Efficient Incrementalized Runtime Checking of Linear Measures on Lists

Alex Gyori, Pranav Garg, Edgar Pek, P. Madhusudan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present mechanisms to specify and efficiently check, at runtime, assertions that express structural properties and aggregate measures of dynamically manipulated linkedlist data structures. Checking assertions involving the structure, disjointness, and aggregation measures on lists and list segments typically requires linear or quadratic time in the size of the heap. Our main contribution is an incrementalization instrumentation that tracks properties of data structures dynamically as the program executes and leads to orders of magnitude speedup in assertion checking in many scenarios. Our incrementalization incurs a constant overhead on updates to list structures but enables checking assertions in constant time, independent of the size of the heap. We define a general class of functions on lists, called linear measures, which are amenable to our incrementalization technique. We demonstrate the effectiveness of our technique by showing orders of magnitude speedup in two scenarios: one scenario stemming from assertions at the level of APIs of list-manipulating libraries and the other scenario stemming from providing dynamic detection of security attacks caused by malicious rootkits.

Original languageEnglish (US)
Title of host publicationProceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages310-320
Number of pages11
ISBN (Electronic)9781509060313
DOIs
StatePublished - May 15 2017
Event10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017 - Tokyo, Japan
Duration: Mar 13 2017Mar 17 2017

Publication series

NameProceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017

Other

Other10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017
CountryJapan
CityTokyo
Period3/13/173/17/17

Keywords

  • Assertion Checking
  • Incrementalization
  • Runtime Verification

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Software

Fingerprint Dive into the research topics of 'Efficient Incrementalized Runtime Checking of Linear Measures on Lists'. Together they form a unique fingerprint.

Cite this