Published in Volume XXII, Issue 2, 2012, pages 327-365, doi: 10.7561/SACS.2012.2.327

Authors: G. Roșu

Abstract

This paper addresses the problem of runtime verification from a foundational perspective, answering questions like “Is there a consensus among the various definitions of a safety property?” (Answer: Yes), “How many safety properties exist?” (Answer: As many as real numbers), “How difficult is the problem of monitoring a safety property?” (Answer: Arbitrarily complex), “Is there any formalism that can express all safety properties?” (Answer: No), etc. Various definitions of safety properties as sets of execution traces have been proposed in the literature, some over finite traces, others over infinite traces, yet others over both finite and infinite traces. By employing cardinality arguments and a novel notion of {em persistence}, this paper first establishes the existence of bijective correspondences between the various notions of safety property. It then shows that safety properties can be characterized as “always past” properties. Finally, it proposes a general notion of {em monitor}, which allows to show that safety properties correspond precisely to the monitorable properties, and then to establish that monitoring a safety property is arbitrarily hard.

Full Text (PDF)

References

[1] Martín Abadi and Leslie Lamport. The existence of refinement mappings. In Proceedings of the Third Annual Symposium on Logic in Computer Science (LICS ’88), pages 165-175. IEEE Computer Society, 1988. http://dx.doi.org/10.1109/LICS.1988.5115 .

[2] Martín Abadi and Leslie Lamport. The existence of refinement mappings. Theoretical Computer Science, 82(2):253-284, 1991. http://dx.doi.org/10.1016/0304-3975(91)90224-P .

[3] Chris Allan, Pavel Avgustinov, Aske Simon Christensen, Laurie Hendren, Sascha Kuzins, Ondrej Lhotak, Oege de Moor, Damien Sereni, Ganesh Sittampalam, and Julian Tibble. Adding trace matching with free variables to AspectJ. In Richard P. Gabriel, editor, ACM Conference on Object-Oriented Programming, Systems and Languages (OOPSLA), pages 345-364. ACM Press, 2005. http://dx.doi.org/10.1145/1094811.1094839 .

[4] Bowen Alpern and Fred B. Schneider. De ning liveness. Information Processing Letters, 21(4):181-185, 1985. http://dx.doi.org/10.1016/0020-0190(85)90056-0 .

[5] Krzysztof R. Apt, Nissim Francez, and Shmuel Katz. Appraising fairness in languages for distributed programming. In Fourteenth Annual ACM Symposium on Principles of Programming Languages (POPL’ 87), pages 189-198, 1987. http://dx.doi.org/10.1145/41625.41642 .

[6] Feng Chen, Marcelo D’Amorim, and Grigore Rosu. Checking and correcting behaviors of Java programs at runtime with Java-MOP. In RV’05, volume 144(4) of Electronic Notes in Theoretical Computer Science. http://dx.doi.org/10.1016/j.entcs.2006.02.002 .

[7] Kevin W. Hamlen, J. Gregory Morrisett, and Fred B. Schneider. Computability classes for enforcement mechanisms. ACM Trans. Program. Lang. Syst., 28(1):175-205, 2006. http://dx.doi.org/10.1145/1111596.1111601 .

[8] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

[9] Leslie Lamport. Proving the correctness of multiprocess programs. IEEE Transactions on Software Engineering., 3(2):125-143, 1977. http://dx.doi.org/10.1109/TSE.1977.229904 .

[10] Leslie Lamport. Logical foundation. In M. W. Alford, J. P. Ansart, G. Hommel, L. Lamport, B. Liskov, G. P. Mullery, F. B. Schneider, M. Paul, and H. J. Siegert, editors, Distributed systems: Methods and tools for specification. An advanced course, volume 190 of LNCS, pages 119-130. Springer-Verlag, 1985.

[11] Zohar Manna and Amir Pnueli. Temporal verification of reactive systems: safety. Springer-Verlag New York, Inc., New York, NY, USA, 1995.

[12] G. Rosu and M. Viswanathan. Testing extended regular language membership incrementally by rewriting. In RTA’03, volume 2706 of Lecture Notes in Computer Science, pages 499-514. Springer, 2003. http://dx.doi.org/10.1007/3-540-44881-0_35 .

[13] Fred B. Schneider. On Concurrent Programming. Springer, 1997.

[14] Fred B. Schneider. Enforceable security policies. ACM Transactions on Information and System Security, 3(1):30-50, 2000. http://dx.doi.org/10.1145/353323.353382 .

Bibtex

@article{sacscuza:rosu2012ospatm,
  title={On Safety Properties and Their Monitoring},
  author={G. Ro{c s}u},
  journal={Scientific Annals of Computer Science},
  volume={22},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2012},
  pages={327--365},
  doi={10.7561/SACS.2012.2.327},
  publisher={``A.I. Cuza'' University Press}
}