Quantitative Analysis of Systems Using Game-Theoretic Learning
Authors:
Open Access
- 1 August 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 11 (S2) , 1-27
Abstract
The analysis of quantitative properties, such as timing and power, is central to the design of reliable embedded software and systems. However, the verification of such properties on a program is made difficult by their heavy dependence on the program’s environment, such as the processor it runs on. Modeling the environment by hand can be tedious, error prone, and time consuming. In this article, we present a new game-theoretic approach to analyzing quantitative properties that is based on performing systematic measurements to automatically learn a model of the environment. We model the problem as a game between our algorithm (player) and the environment of the program (adversary) in which the player seeks to accurately predict the property of interest, while the adversary sets environment states and parameters. To solve this problem, we employ a randomized strategy that repeatedly tests the program along a linear-sized set of program paths called basis paths, using the resulting measurements to infer a weighted-graph model of the environment from which quantitative properties can be predicted. Test cases are automatically generated using satisfiability modulo theories (SMT) solving. We prove that our algorithm can, under certain assumptions and with arbitrarily high probability, accurately predict properties such as worst-case execution time or estimate the distribution of execution times. Experimental results for execution time analysis demonstrate that our approach is efficient, accurate, and highly portable.Keywords
Funding Information
- Division of Computer and Network Systems (CNS-0644436)
- Defense Advanced Research Projects Agency (FA8750-05-2-0249)
This publication has 13 references indexed in Scilit:
- Quantitative Analysis of Embedded Software Using Game-Theoretic Learning2009
- The worst-case execution-time problem—overview of methods and survey of toolsACM Transactions on Embedded Computing Systems, 2008
- Prediction, Learning, and Games2006
- An overview of the competitive and adversarial approaches to designing dynamic power management strategiesIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2005
- Verifying Quantitative Properties Using Bound FunctionsLecture Notes in Computer Science, 2005
- Adaptive routing with end-to-end feedback2004
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- Finding the k Shortest PathsSIAM Journal on Computing, 1998
- A Complexity MeasureIEEE Transactions on Software Engineering, 1976
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952