Monitoring hyperproperties over observed and constructed traces

Chalupa M, Henzinger TA, Oliveira da Costa A. 2026. Monitoring hyperproperties over observed and constructed traces. 26th International Conference on Runtime Verification. RV: Runtime Verification, LNCS, vol. 17117, 351–371.

Download (ext.)

Conference Paper | Published | English

Scopus indexed

Corresponding author has ISTA affiliation

Series Title
LNCS
Abstract
Hyperproperties specify system requirements that relate multiple executions. Reasoning about such properties naturally involves executions that play different roles: some correspond to concrete behaviors of the system under verification, while others represent idealized or alternative executions defined by the specification. We propose a framework that makes this semantic distinction explicit by distinguishing between observed and constructed traces. Constructed traces are built using generators: functions provided at specification time and invoked by monitors at runtime. Our main motivation lies in the runtime verification of hyperproperties, where only a finite view on possible executions is available. Our approach enables sound runtime verification for a broader class of hyperproperties than approaches that do not account for constructed traces, including properties with quantifier alternation, such as opacity in security, and properties defined with respect to idealized executions, such as linearizability in concurrency. We present a monitoring algorithm incorporating generator-constructed traces, and evaluate it on hyperproperties ranging from security to concurrency, demonstrating that constructed traces not only broaden expressivity but can also significantly accelerate violation detection.
Publishing Year
Date Published
2026-10-07
Proceedings Title
26th International Conference on Runtime Verification
Publisher
Springer
Acknowledgement
This work was supported in part by the European Research Council (ERC) Grant VAMOS (No. 101020093), the Austrian Science Fund (FWF) SFB project SpyCoDe 10.55776/F85, and by the Advanced Research and Invention Agency under the Safeguarded AI programme (MSAI-PR01-P047).
Volume
17117
Page
351-371
Conference
RV: Runtime Verification
Conference Location
Kingston, ON, Canada
Conference Date
2026-10-06 – 2026-10-09
ISSN
eISSN
IST-REx-ID

Cite this

Chalupa M, Henzinger TA, Oliveira da Costa A. Monitoring hyperproperties over observed and constructed traces. In: 26th International Conference on Runtime Verification. Vol 17117. Springer; 2026:351-371. doi:10.1007/978-3-032-41160-0_22
Chalupa, M., Henzinger, T. A., & Oliveira da Costa, A. (2026). Monitoring hyperproperties over observed and constructed traces. In 26th International Conference on Runtime Verification (Vol. 17117, pp. 351–371). Kingston, ON, Canada: Springer. https://doi.org/10.1007/978-3-032-41160-0_22
Chalupa, Marek, Thomas A Henzinger, and Ana Oliveira da Costa. “Monitoring Hyperproperties over Observed and Constructed Traces.” In 26th International Conference on Runtime Verification, 17117:351–71. Springer, 2026. https://doi.org/10.1007/978-3-032-41160-0_22.
M. Chalupa, T. A. Henzinger, and A. Oliveira da Costa, “Monitoring hyperproperties over observed and constructed traces,” in 26th International Conference on Runtime Verification, Kingston, ON, Canada, 2026, vol. 17117, pp. 351–371.
Chalupa M, Henzinger TA, Oliveira da Costa A. 2026. Monitoring hyperproperties over observed and constructed traces. 26th International Conference on Runtime Verification. RV: Runtime Verification, LNCS, vol. 17117, 351–371.
Chalupa, Marek, et al. “Monitoring Hyperproperties over Observed and Constructed Traces.” 26th International Conference on Runtime Verification, vol. 17117, Springer, 2026, pp. 351–71, doi:10.1007/978-3-032-41160-0_22.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Metadata Export

Sources

arXiv 2508.02301

Search this title in

Google Scholar
ISBN Search