Simulating midlet's security claims with automata modulo theory

Model-carrying code and security-by-contract have proposed to augment mobile code with a claim on its security behavior that could be matched against a mobile platform policy before downloading the code. In order to capture realistic scenarios with potentially infinite transitions (e.g. "only connections to urls starting with https") we have proposed to represent those policies with the notion of Automata Modulo Theory (AMT), an extension of Büchi Automata (BA), with edges labeled by expressions in a decidable theory. Our objective is the run-time matching of the mobile's platform policy against the midlet's security claims expressed as AMT. To this extent the use of on-the-fly product and emptiness test from automata theory may not be effective. In this paper we present an algorithm extending fair simulation between Büchi automata that can be more efficiently implemented. Copyright © 2008 ACM.