Machine Learning (EdgeML) algorithms on edge devices facilitate safety-critical applications like building security management and smart city interventions. However, their wired/wireless connections with the Internet make such platforms vulnerable to attacks compromising the embedded software. We find that in the prior works, the issue of regular runtime integrity assessment of the deployed software with negligible EdgeML performance degradation is still unresolved. In this paper, we present PracAttest, a practical runtime attestation framework for embedded devices running compute-heavy EdgeML applications. Unlike the conventional remote attestation schemes that check the entire software in each attestation event, PracAttest segments the software and randomizes the integrity check of these segments over short random attestation intervals. The segmentation coupled with the randomization leads to a novel performance-vs-security trade-off that can be tuned per the EdgeML application’s performance requirements. Additionally, we implement three realistic EdgeML benchmarks for pollution measurement, traffic intersection control, and face identification, using state-of-the-art neural network and computer vision algorithms. We specify and verify security properties for these benchmarks and evaluate the efficacy of PracAttest in attesting the verified software. PracAttest provides 50x-80x speedup over the state-of-the-art baseline in terms of mean attestation time, with negligible impact on application performance. We believe that the novel performance-vs-security trade-off facilitated by PracAttest will expedite the adoption of runtime attestation on edge platforms.