REVIEW 4 major objections 5 minor 30 references
Monitoring in the Dark: Privacy-Preserving Runtime Verification of Cyber-Physical Systems
T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Garbled circuits can make runtime verification of cyber-physical systems privacy-preserving, so a monitor checks a system's timed trace against a secret specification and both parties learn only the robustness score.
desk verdict First garbled-circuit STL robustness monitor, but the variable-clock-cycle leak undercuts the privacy claim until a fixed-cycle implementation is used. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is a synthesizable hardware implementation of DP-TALIRO, a dynamic program that computes STL robustness by filling an $N_x \times M$ table: one column per sub-formula, one row per trace sample, starting at the end of the trace and ending at $\rho(x,\varphi,0)$. The circuit is written as a controller-plus-datapath design in Verilog, with a finite-state machine handling the formula's syntax and a BOUNDS module computing the index ranges for temporal intervals; after synthesis the netlist is evaluated inside a sequential garbled-circuit protocol, which is what turns a public computation into a private two-party one. Because the formula itself is an input to the circuit, the same netlist serves any formula up to a fixed depth, so the circuit size does not leak the formula; only the agreed maximum depth and trace length are common knowledge. Sequential gates (flip-flops) keep the circuit small, and the protocol's communication complexity is $O(C \cdot cc \cdot \kappa)$ bits for circuit size $C$, clock cycles $cc$, and security parameter $\kappa$, while memory is $O(C\cdot\kappa)$.
What would settle it
Compare the circuit's output against a trusted reference implementation of DP-TALIRO on a large random corpus of traces and formulas; any input pair for which the sign or numeric value of $\rho(x,\varphi,0)$ differs would refute the claim that the circuit is a faithful robustness monitor.
Extended reading notes
Core claim
The central discovery is that the robustness-monitoring computation itself—not just satisfiability—can be run inside a garbled circuit, so the quantitative verdict is private by construction. The protocol has two parties: the Designer, who holds a finite timed trace of samples, and the Verifier, who holds an STL formula. They agree on a circuit that accepts both as inputs and outputs the robustness value $\rho(x,\varphi,0)$; following the garbled-circuit protocol, each party learns this value and nothing else beyond input lengths, with formulas padded to a fixed maximum depth to hide their true length. The circuit implements the DP-TALIRO dynamic program, which fills a table of robustness values indexed by trace positions and sub-formulas, and a BOUNDS subroutine that finds the timestamps inside a temporal interval. The paper reports that a gate-level netlist synthesized from Verilog, evaluated through a sequential garbled-circuit engine, computes robustness for traces up to length 500 and formulas of depth 4, with memory use linear in trace length and runtime growing roughly exponentially in trace length in software, while the number of hardware clock cycles suggests that a hardware implementation would be much faster. The authors take this as evidence that private monitoring is feasible today for testing and offline monitoring, and would be practical online once garbled circuits run in hardware.
Load-bearing premise
The whole practical claim rests on the synthesized circuit computing exactly the same robustness values as DP-TALIRO on fixed 32-bit scaled integers; the paper gives no formal equivalence proof between the Verilog and the algorithm, so a silent bug in the circuit would produce a wrong verdict while still satisfying the privacy guarantee.
Editorial extensions
If this is right
- In software, the private monitor is fast enough for short inputs: a trace of length 10 with a depth-3 formula takes about one second, which is acceptable in a testing loop when simulation of the system under test dominates the cost.
- Peak memory grows linearly with trace length, so a device with 1 GB of RAM can in principle handle a trace of 500 samples and a depth-4 formula, making embedded deployment plausible on the memory axis.
- Because the synthesized circuit is independent of the particular formula and trace, it can be synthesized once, offline, on a powerful machine and then reused for arbitrary monitoring sessions, amortizing the high synthesis cost.
- If garbled circuits are implemented directly in hardware, the measured clock-cycle counts indicate online monitoring could become practical; the paper estimates 40,000 cycles at 2.1 GHz as 19 ms, which is in the range of real-time control loops.
Reading between the lines
- The paper leaves implicit that padding formulas and traces to fixed maxima converts the protocol's known input-length leakage into merely an upper bound, so a deployment could pad beyond the actual values and reveal even less than the nominal lengths.
- The semi-honest threat model is what the measurements target; hardening the protocol against a malicious system owner or monitor would require additional proofs or zero-knowledge machinery, and the added overhead is not included in the reported runtimes.
- A hardware garbled-circuit engine is the natural next experiment: running the same netlist on such an engine would directly test the authors' conjecture that online monitoring becomes practical, and would let engineers measure whether the 19 ms estimate holds at full circuit scale.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a privacy-preserving runtime monitoring protocol in which a Designer holds a timed trace and a Verifier holds an STL formula, and both parties learn only the robustness of the trace with respect to the formula. The protocol is based on garbled circuits: DP-TALIRO is implemented as a parameterized Verilog sequential circuit that accepts both the trace and the formula as inputs, the netlist is synthesized with Synopsys Design Compiler, and the resulting circuit is garbled and evaluated with TinyGarble. The paper reports circuit sizes, clock-cycle counts, software runtime, peak memory, and synthesis time for traces up to length 500 and formulas of depth 3 and 4, and concludes that the approach is feasible for design testing and offline monitoring and for short traces in online monitoring. The authors state that security is inherited from standard garbled-circuit security, and that correctness of the underlying algorithm is inherited from DP-TALIRO.
Significance. If the result holds, this is the first garbled-circuit implementation of STL robustness monitoring over timed state sequences, and it is a useful feasibility baseline for private runtime verification. The paper has real strengths: security is inherited from the standard Bellare-Hoang-Rogaway garbled-circuits model rather than from an ad hoc primitive; the circuit is parameterized by maximum trace length and formula depth, so the formula is an input rather than compiled per formula; and the experimental evaluation makes concrete, falsifiable claims about runtime, clock cycles, memory, and synthesis time. However, the strongest privacy claim is not met by the reported implementation because the number of clock cycles varies with the formula, and the correctness of the synthesized circuit relative to DP-TALIRO is asserted rather than demonstrated. Both issues are fixable, but they are load-bearing for the central contribution.
major comments (4)
- [§4.2, §5.1, §6 (Fig. 6)] The implementation as reported does not realize the claimed guarantee that the system 'learns nothing about the formula.' The controller in §4.2 is an FSM whose control path depends on the formula's operator types and temporal intervals (e.g., the U_ZERO_UNB branch for [0,∞) and the looping branch for general [a,b) intervals), and Fig. 6 explicitly shows different clock-cycle counts for different formulas of the same depth and trace length. In a TinyGarble-style sequential garbled circuit, each clock cycle is a separate garbled-evaluation step, so the number of cycles is observable to both parties through execution time and communication volume. The ideal-world model in §2.3 allows leakage only of maximum input lengths and the output, not of the actual number of evaluation rounds. The paper itself acknowledges in §6 that 'an industrial implementation would run for a fixed number of cycles regardless of the formula,' confirming that the reported implementation is not constant-cycle. To meet the stated privacy claim, the protocol must fix a maximum cycle count and pad all evaluations to that count; the security statement and all reported measurements must then refer to the padded circuit.
- [§4.1–4.2, §6] The paper provides no correctness evidence that the Verilog RTL computes DP-TALIRO and hence the STL robustness function. Correctness of DP-TALIRO is cited to [29], and the RTL is described informally as a controller/datapath implementation of Algorithm 1, but there is no equivalence proof between Algorithm 1 and the RTL, no systematic test suite covering all operator types and interval boundary cases, and no theorem about the 32-bit fixed-point integer scaling introduced in §6 (signal values, timestamps, formula thresholds, and interval endpoints are all scaled by 10^5). If the synthesized circuit computes a different function than the true robustness, the privacy guarantee is vacuous because both parties learn the output of the wrong computation. A revision should add a formal or at least rigorous differential verification of the RTL and synthesized netlist against a reference DP-TALIRO implementation, including overflow behavior of the scaled arithmetic.
- [§5.2, §6 (Fig. 5), §7] The paper's claim that runtime 'scales exponentially with the size of the inputs' and that 'execution time in software scales exponentially with the trace length' is not supported by its own complexity model. Section 5.2 bounds the total work and communication by O(C·cc·κ), Fig. 9 reports circuit size C as linear in trace length, and DP-TALIRO is a dynamic program over N_x·M table entries, so even a conservative bound on the clock-cycle count cc is polynomial in N_x and formula depth for the bounded loops used in this implementation. The steep increase visible in Fig. 5 may reflect implementation overheads or fitting artifacts, but the paper gives no fitted functional form or confidence bounds. Please replace the exponential claim with a precise statement about the measured clock-cycle scaling, or with fitted curves and their error measures, and adjust the practicability discussion in §6 and §7 accordingly.
- [§6] The empirical evaluation is the basis for the feasibility claims, but the manuscript provides no code, Verilog sources, synthesized netlists, or raw data. Without these artifacts, the reported runtimes, memory usage, and synthesis times cannot be reproduced, and the claimed equivalence of the synthesized circuit to DP-TALIRO cannot be checked beyond the illustrative example in Table 3. I request that the artifacts be made available with the revision; if this is impossible, the empirical claims should be explicitly marked as preliminary and the paper should state what would be needed to reproduce them.
minor comments (5)
- [§2.1, Eq. (5)] In the Until robustness definition, the left-hand side uses the evaluation time variable t while the right-hand side uses the index i inside t^{-1}(t(i)+I); please make the notation consistent.
- [§4.1] Algorithm 1 returns R[1,1], while the text says 'the final value located at entry[0,0]'; Table 3 also uses row index 0. Please standardize the indexing convention.
- [§6] The fitted curves in Figs. 5–7 are described only as 'best fit'; please report the fitted functional forms and error measures, since the exponential-vs-polynomial interpretation in the text hinges on those curves.
- [§1] The sentence 'We show that privacy-preserving monitoring or CPS is indeed feasible' appears to contain a typo; it should likely read 'of CPS.'
- [§5.1] The claim that padding a shorter formula with 1-bits 'does not impact the robustness calculation' depends on the circuit's formula decoder treating padded subtrees as neutral for every operator encoding; please state this design invariant explicitly.
Circularity Check
No significant circularity: the privacy claim rests on external garbled-circuit security and an externally validated robustness algorithm, with empirical measurements rather than predictions.
full rationale
The paper's central derivation chain is not circular. The privacy guarantee is inherited from standard garbled-circuit security, cited to the external Bellare-Hoang-Rogaway foundations in [3], and the ideal-world model in Section 2.3 is an independent framing rather than a self-supplied theorem. The monitored function itself is DP-TALIRO, adopted from the external work [29], whose correctness is cited to that external source; the Verilog circuit is described as an implementation of that algorithm, and any gap between the RTL and Algorithm 1 is a correctness risk, not a circular reduction. The runtime, memory, and clock-cycle figures in Section 6 are measured experimental characterizations, not predictions derived from the target claim. The only self-citations ([1] and [16]) are motivational or related-work references and do not carry the proof burden. The acknowledged variable-clock-cycle leak in Section 6 is a privacy gap relative to the stated ideal functionality, but it is not a case of fitting an input and renaming it as a prediction, nor of defining one quantity in terms of another. Accordingly, no circular step is present and the score is 0.
Assumptions & free parameters
free parameters (1)
- integer scaling factor =
10^5
assumptions (5)
- domain assumption Security of Yao garbled circuits under the semi-honest model
- domain assumption Correctness of DP-TALIRO
- domain assumption STL robustness semantics over timed state sequences with half-open intervals
- domain assumption Faithful synthesis and garbling of the Verilog design
- ad hoc to paper No overflow in 32-bit arithmetic
Cite this review
Pith. "Pith review of Monitoring in the Dark: Privacy-Preserving Runtime Verification of Cyber-Physical Systems." pith.science (2026). https://pith.science/paper/32YE2QGS
@misc{pith2026250516059,
author = {Pith},
title = {Pith review of: Monitoring in the Dark: Privacy-Preserving Runtime Verification of Cyber-Physical Systems},
year = {2026},
howpublished = {\url{https://pith.science/paper/32YE2QGS}},
note = {Machine review of arXiv:2505.16059}
}
read the original abstract
In distributed Cyber-Physical Systems and Internet-of-Things applications, the nodes of the system send measurements to a monitor that checks whether these measurements satisfy given formal specifications. For instance in Urban Air Mobility, a local traffic authority will be monitoring drone traffic to evaluate its flow and detect emerging problematic patterns. Certain applications require both the specification and the measurements to be private -- i.e. known only to their owners. Examples include traffic monitoring, testing of integrated circuit designs, and medical monitoring by wearable or implanted devices. In this paper we propose a protocol that enables privacy-preserving robustness monitoring. By following our protocol, both system (e.g. drone) and monitor (e.g. traffic authority) only learn the robustness of the measured trace w.r.t. the specification. But the system learns nothing about the formula, and the monitor learns nothing about the signal monitored. We do this using garbled circuits, for specifications in Signal Temporal Logic interpreted over timed state sequences. We analyze the runtime and memory overhead of privacy preservation, the size of the circuits, and their practicality for three different usage scenarios: design testing, offline monitoring, and online monitoring of Cyber-Physical Systems.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[29]
Hengyi Yang, Georgios Fainekos, Hessam Sarjoughian, and Aviral Shrivastava. 2013. Dynamic programming algorithm for computing temporal logic robustness . Ph. D. Dissertation. Arizona State University. , Vol. 1, No. 1, Article . Publication date: September 2025
work page 2013
-
[1]
Houssam Abbas. 2019. Work-In-Progress: Private Runtime Verification. In 2019 International Conference on Embedded Software (EMSOFT). Association for Computing Machinery, New York, NY, United States, 1–2
work page 2019
-
[2]
Ryotaro Banno, Kotaro Matsuoka, Naoki Matsumoto, Song Bian, Masaki Waga, and Kohei Suenaga. 2022. Oblivious Online Monitoring for Safety LTL Specification via Fully Homomorphic Encryption. In Computer Aided Verification, Sharon Shoham and Yakir Vizel (Eds.). Springer International Publishing, Cham, 447–468
work page 2022
-
[3]
Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. 2012. Foundations of garbled circuits. In Proceedings of the 2012 ACM Conference on Computer and Communications Security (Raleigh, North Carolina, USA) (CCS ’12). Association for Computing Machinery, New York, NY, USA, 784–796. https://doi.org/10.1145/2382196.2382279
arXiv 2012
-
[4]
Marina Blanton and Mehrdad Aliasgari. 2010. Secure Outsourcing of DNA Searching via Finite Automata. In Data and Applications Security and Privacy XXIV , Sara Foresti and Sushil Jajodia (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 49–64
work page 2010
-
[5]
Dan Boneh and Victor Schoup. 2023. A Graduate Course in Applied Cryptography . Available Online. Version 0.6
work page 2023
-
[6]
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2020. TFHE: fast fully homomorphic encryption over the torus. Journal of Cryptology 33, 1 (2020), 34–91
work page 2020
-
[7]
W.T. Councill. 1999. Third-party testing and the quality of software components. IEEE Software 16, 4 (1999), 55–57. https://doi.org/10.1109/52.776949
Show all 30 references
-
[8]
Darko Stern (AVL). 2024. Personal Communication. AVL List GmbH (“AVL”) is one of the world’s leading mobility technology companies for development, simulation and testing in the automotive industry. Website avl.com accessed February 15, 2024
2024
-
[9]
Zhi Jie Dong, Mohamed H Zaki, Ghiath Al Sammane, Sofiene Tahar, and Guy Bois. 2007. Run-time verification using the VHDL-AMS simulation environment. In 2007 IEEE Northeast Workshop on Circuits and Systems . IEEE, Montreal, Canada, 1513–1516. https://doi.org/10.1109/NEWCAS.2007.4488030
2007
-
[10]
David Evans, Vladimir Kolesnikov, and Mike Rosulek. 2018. A pragmatic introduction to secure multi-party computation. Foundations and Trends® in Privacy and Security 2, 2-3 (2018), 70–246
2018
-
[11]
Fainekos and George J
Georgios E. Fainekos and George J. Pappas. 2009. Robustness of temporal logic specifications for continuous-time signals. Theor. Comput. Sci. 410, 42 (Sept. 2009), 4262–4291. https://doi.org/10.1016/j.tcs.2009.06.021
2009 doi
-
[12]
Stefan Jakšić, Ezio Bartocci, Radu Grosu, Reinhard Kloibhofer, Thang Nguyen, and Dejan Ničkovié. 2015. From signal temporal logic to FPGA monitors. In 2015 ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE). IEEE, Austin, TX, USA, 218–227
2015
-
[13]
Jianqiao Mo, Jayanth Gopinath, and Brandon Reagen. 2023. Haac: A hardware-software co-design to accelerate garbled circuits. In Proceedings of the 50th Annual International Symposium on Computer Architecture . ACM, Orlando, FL, USA, 1–13
2023
-
[14]
Mo and B
Y. Mo and B. Sinopoli. 2009. Secure control against replay attacks. In 2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton) . 911–918. https://doi.org/10.1109/ALLERTON.2009.5394956
2009
-
[15]
Dejan Nickovic and Oded Maler. 2007. AMT: A Property-Based Monitoring Tool for Analog Systems. In FORMATS (LNCS, Vol. 4763). Springer, 304–319
2007
-
[16]
Unmesh Patil, Jinhoong Choi, and Houssam Abbas. 2024. OUT-HERD: Opportunistic UAV Takeover for Herding Malfunctioning Drones. In 27th IEEE International Conference on Intelligent Transportation Systems (ITSC) . IEEE
2024
-
[17]
Thomas Reinbacher, Matthias Függer, and Jörg Brauer. 2012. Real-time runtime verification on chip. In International Conference on Runtime Verification. Springer, Istanbul, Turkey, 110–125
2012
-
[18]
Hirohito Sasakawa, Hiroki Harada, David duVerle, Hiroki Arimura, Koji Tsuda, and Jun Sakuma. 2014. Oblivious Evaluation of Non-deterministic Finite Automata with Application to Privacy-Preserving Virus Genome Detection. In Proceedings of the 13th Workshop on Privacy in the Ele...
2014
-
[19]
Ebrahim M Songhori, Siam U Hussain, Ahmad-Reza Sadeghi, Thomas Schneider, and Farinaz Koushanfar. 2015. Tinygarble: Highly compressed and scalable sequential garbled circuits. In 2015 IEEE Symposium on Security and Privacy. IEEE, IEEE, San Jose, CA, USA, 411–428
2015
-
[20]
cadence.com 2024. Cadence. Accessed February 15, 2024
2024
-
[21]
GF Micro
gfmicro.com 2024. GF Micro. Accessed February 15, 2024
2024
-
[22]
https://testlio.com 2024. Testlio. Accessed March 10, 20024
2024
-
[23]
https://www.collinsaerospace.com/what-we-do/industries/commercial-aviation/aerostructures/aerospace-test-labs
-
[24]
https://www.grandviewresearch.com/industry-analysis/testing-as-a-service-market-report 2024. Testing As A Service Market Size, Share & Trends Analysis Report By Test Type (Functionality, Security, Compliance), By Deployment Type, By End-use, By Region, And Segment Forecasts, 2...
2024
-
[25]
Third-Party Laboratory Testing of Semiconductor Market: Trends, Opportunities and Competitive Analysis [2023-2028]
https://www.lucintel.com/third-party-laboratory-testing-of-semiconductor-market.aspx 2023. Third-Party Laboratory Testing of Semiconductor Market: Trends, Opportunities and Competitive Analysis [2023-2028]. Accessed September 11, 2024
2023
-
[26]
Rainforest QA
https://www.rainforestqa.com/features/test-automation 2024. Rainforest QA. Accessed March 10, 20024
2024
-
[27]
Global Semiconductor Third-party Testing Services Market Growth (Status and Outlook) 2024-2031
https://www.reliableresearchreports.com/ 2024. Global Semiconductor Third-party Testing Services Market Growth (Status and Outlook) 2024-2031. Accessed February 15, 2024
2024
-
[28]
rambus.com 2024. Rambus. Accessed February 15, 2024
2024
-
[2024]
Accessed February 15, 2024
Collins Aerospace Test Labs. Accessed February 15, 2024. , Vol. 1, No. 1, Article . Publication date: September 2025. 18 Koll et al
2024
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.