Vinayak S. Prabhu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Vinayak S. Prabhu has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Rupak Majumdar
Max Planck Institute for Software Systems (MPI-SWS), Kaiserslautern, Germany
5 shared publications - Jyotirmoy V. Deshmukh
Toyota Technical Center
3 shared publications - Bassem Ghorbel
Colorado State University, USA
2 shared publications - Indrajit Ray
Colorado State University, Fort Collins, Colorado, USA
1 shared publication - Indrakshi Ray
Colorado State University
1 shared publication - Mohit Singh
Department of Production Engineering, Guru Nanak Dev Engineering College, Ludhiana, India
1 shared publication
Latest Publications
- Open Access
- 14 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-12
Fast and Scalable Monitoring for Value-Freeze Operator augmented Signal Temporal Logic
Signal Temporal Logic (STL) is a timed temporal logic formalism that has found widespread adoption for rigorous specification of properties in Cyber-Physical Systems. However, STL is unable to specify oscillatory properties commonly required in engineering design. This limitation can be overcome by the addition of additional operators, for example, signal-value freeze operators, or with first order quantification. Previous work on augmenting STL with such operators has resulted in intractable monitoring algorithms. We present the first efficient and scalable offline monitoring algorithms for STL augmented with independent freeze quantifiers. Our final optimized algorithm has a |ρ|log (|ρ|) dependence on the trace length |ρ| for most traces ρ arising in practice, and a |ρ|2 dependence in the worst case. We also provide experimental validation of our algorithms – we show the algorithms scale to traces having 100k time samples.
- 14 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-12
Open AccessFast and Scalable Monitoring for Value-Freeze Operator augmented Signal Temporal Logic
Signal Temporal Logic (STL) is a timed temporal logic formalism that has found widespread adoption for rigorous specification of properties in Cyber-Physical Systems. However, STL is unable to specify oscillatory properties commonly required in engineering design. This limitation can be overcome by the addition of additional operators, for example, signal-value freeze operators, or with first order quantification. Previous work on augmenting STL with such operators has resulted in intractable monitoring algorithms. We present the first efficient and scalable offline monitoring algorithms for STL augmented with independent freeze quantifiers. Our final optimized algorithm has a |ρ|log (|ρ|) dependence on the trace length |ρ| for most traces ρ arising in practice, and a |ρ|2 dependence in the worst case. We also provide experimental validation of our algorithms – we show the algorithms scale to traces having 100k time samples.
- 6 June 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 42 (12) , 4436-4449
Quantitative Robustness for Signal Temporal Logic With Time-Freeze Quantifiers
Signal temporal logic (STL) is a variant of metric temporal logic (MTL) which can express intricate temporal requirements over signals and has found wide adoption for expressing requirements over complex control systems models. A key factor in the success of STL has been that of quantitative robustness, and the development of efficient algorithms for computing the robustness values over traces. The real-valued quantitative robustness of a signal with respect to an STL property quantifies the degree of satisfaction or violation of the property by the signal. In this work, we introduce a notion of robustness for a more expressive logic, timed STL (TSTL), which can be seen as timed propositional temporal logic (TPTL) with predicates defined over real-valued signals. This logic can express many natural engineering requirements that STL cannot. We also develop algorithms for computing this robustness value over traces in the pointwise semantics. While the robustness computation for general TSTL formulas is PSPACE-hard due to the PSPACE-hardness of the monitoring problem for TPTL, for the special case of one variable TSTL, a fragment of TSTL which is still more expressive than STL, we develop an optimized algorithm which computes robustness in time linear in the length of the trace. Finally, we experimentally validate the tractability of our algorithms with our prototype tool in MATLAB.
- 6 June 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 42 (12) , 4436-4449
Quantitative Robustness for Signal Temporal Logic With Time-Freeze Quantifiers
Signal temporal logic (STL) is a variant of metric temporal logic (MTL) which can express intricate temporal requirements over signals and has found wide adoption for expressing requirements over complex control systems models. A key factor in the success of STL has been that of quantitative robustness, and the development of efficient algorithms for computing the robustness values over traces. The real-valued quantitative robustness of a signal with respect to an STL property quantifies the degree of satisfaction or violation of the property by the signal. In this work, we introduce a notion of robustness for a more expressive logic, timed STL (TSTL), which can be seen as timed propositional temporal logic (TPTL) with predicates defined over real-valued signals. This logic can express many natural engineering requirements that STL cannot. We also develop algorithms for computing this robustness value over traces in the pointwise semantics. While the robustness computation for general TSTL formulas is PSPACE-hard due to the PSPACE-hardness of the monitoring problem for TPTL, for the special case of one variable TSTL, a fragment of TSTL which is still more expressive than STL, we develop an optimized algorithm which computes robustness in time linear in the length of the trace. Finally, we experimentally validate the tractability of our algorithms with our prototype tool in MATLAB.
- Open Access
- 30 May 2022
- Published by Association for Computing Machinery (ACM)
- Vol. 21, 27-38
Detecting Secure Memory Deallocation Violations with CBMC
Scrubbing sensitive data before releasing memory is a widely accepted but often ignored programming practice for developing secure software. Consequently, confidential data such as cryptographic keys, passwords, and personal data, can remain in memory indefinitely, thereby increasing the risk of exposure to hackers who can retrieve the data using memory dumps or exploit vulnerabilities such as Heartbleed and Etherleak. We propose an approach for detecting a specific memory safety bug called Improper Clearing of Heap Memory Before Release, also known as Common Weakness Enumeration 244, in C programs. The CWE-244 bug in a program allows the leakage of confidential information when a variable is not wiped before heap memory is freed. Our approach combines taint analysis and model checking to detect this weakness. We have three main phases: (1) perform a coarse flow-insensitive inter-procedural static analysis on the program to construct a set of pointer variables that could point to sensitive data; (2) instrument the program with required dynamic variable tracking, and assertion logic for memory wiping before deallocation; and (3) invoke a model checker, the C-Bounded Model Checker (CBMC) in our case, to detect assertion violation in the instrumented program. We develop a tool, \toolname, implementing our instrumentation based algorithm, and we provide experimental validation on the Juliet Test Suite --- the tool is able to detect all the CWE-244 instances present in the test suite. To the best of our knowledge, this is the first work which presents a solution to the problem of detecting unscrubbed secure memory deallocation violations in programs.
- 30 May 2022
- Published by Association for Computing Machinery (ACM)
- Vol. 21, 27-38
Open AccessDetecting Secure Memory Deallocation Violations with CBMC
Scrubbing sensitive data before releasing memory is a widely accepted but often ignored programming practice for developing secure software. Consequently, confidential data such as cryptographic keys, passwords, and personal data, can remain in memory indefinitely, thereby increasing the risk of exposure to hackers who can retrieve the data using memory dumps or exploit vulnerabilities such as Heartbleed and Etherleak. We propose an approach for detecting a specific memory safety bug called Improper Clearing of Heap Memory Before Release, also known as Common Weakness Enumeration 244, in C programs. The CWE-244 bug in a program allows the leakage of confidential information when a variable is not wiped before heap memory is freed. Our approach combines taint analysis and model checking to detect this weakness. We have three main phases: (1) perform a coarse flow-insensitive inter-procedural static analysis on the program to construct a set of pointer variables that could point to sensitive data; (2) instrument the program with required dynamic variable tracking, and assertion logic for memory wiping before deallocation; and (3) invoke a model checker, the C-Bounded Model Checker (CBMC) in our case, to detect assertion violation in the instrumented program. We develop a tool, \toolname, implementing our instrumentation based algorithm, and we provide experimental validation on the Juliet Test Suite --- the tool is able to detect all the CWE-244 instances present in the test suite. To the best of our knowledge, this is the first work which presents a solution to the problem of detecting unscrubbed secure memory deallocation violations in programs.
- Open Access
- 3 January 2019
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 286, 31-33
Causality Analysis for Concurrent Reactive Systems (Extended Abstract)
We present a comprehensive language theoretic causality analysis framework for explaining safety property violations in the setting of concurrent reactive systems. Our framework allows us to uniformly express a number of causality notions studied in the areas of artificial intelligence and formal methods, as well as define new ones that are of potential interest in these areas. Furthermore, our formalization provides means for reasoning about the relationships between individual notions which have mostly been considered independently in prior work; and allows us to judge the appropriateness of the different definitions for various applications in system design. In particular, we consider causality analysis notions for debugging, error resilience, and liability resolution in concurrent reactive systems. Finally, we present automata-based algorithms for computing various causal sets based on our language-theoretic encoding, and derive the algorithmic complexities.
- 3 January 2019
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 286, 31-33
Open AccessCausality Analysis for Concurrent Reactive Systems (Extended Abstract)
We present a comprehensive language theoretic causality analysis framework for explaining safety property violations in the setting of concurrent reactive systems. Our framework allows us to uniformly express a number of causality notions studied in the areas of artificial intelligence and formal methods, as well as define new ones that are of potential interest in these areas. Furthermore, our formalization provides means for reasoning about the relationships between individual notions which have mostly been considered independently in prior work; and allows us to judge the appropriateness of the different definitions for various applications in system design. In particular, we consider causality analysis notions for debugging, error resilience, and liability resolution in concurrent reactive systems. Finally, we present automata-based algorithms for computing various causal sets based on our language-theoretic encoding, and derive the algorithmic complexities.
- 9 November 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 64 (8) , 3324-3331
Shrinking Horizon Model Predictive Control With Signal Temporal Logic Constraints Under Stochastic Disturbances
We present shrinking horizon model predictive control for discrete-time linear systems under stochastic disturbances with constraints encoded as Signal Temporal Logic (STL) specification. The control objective is to satisfy a given STL specification with high probability against stochastic uncertainties while maximizing the robust satisfaction of an STL specification with minimum control effort. We formulate a general solution, which does not require precise knowledge of probability distributions of (possibly dependent) stochastic disturbances; only the bounded support of the density functions and moment intervals are used. For the specific case of disturbances that are normally distributed, we optimize the controllers by utilizing knowledge of the probability distribution of the disturbance. We show that in both cases, the control law can be obtained by solving optimization problems with linear constraints at each step. We experimentally demonstrate effectiveness of this approach by synthesizing a controller for an HVAC system.
- 9 November 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 64 (8) , 3324-3331
Shrinking Horizon Model Predictive Control With Signal Temporal Logic Constraints Under Stochastic Disturbances
We present shrinking horizon model predictive control for discrete-time linear systems under stochastic disturbances with constraints encoded as Signal Temporal Logic (STL) specification. The control objective is to satisfy a given STL specification with high probability against stochastic uncertainties while maximizing the robust satisfaction of an STL specification with minimum control effort. We formulate a general solution, which does not require precise knowledge of probability distributions of (possibly dependent) stochastic disturbances; only the bounded support of the density functions and moment intervals are used. For the specific case of disturbances that are normally distributed, we optimize the controllers by utilizing knowledge of the probability distribution of the disturbance. We show that in both cases, the control law can be obtained by solving optimization problems with linear constraints at each step. We experimentally demonstrate effectiveness of this approach by synthesizing a controller for an HVAC system.
- Open Access
- 12 April 2017
- Published by Springer Nature in Formal Methods in System Design
- Vol. 50 (2-3) , 168-206
Quantifying conformance using the Skorokhod metric
- 12 April 2017
- Published by Springer Nature in Formal Methods in System Design
- Vol. 50 (2-3) , 168-206
Open AccessQuantifying conformance using the Skorokhod metric
- Open Access
Computing Distances between Reach Flowpipes
We investigate quantifying the difference between two hybrid dynamical systems under noise and initial-state uncertainty. While the set of traces for these systems is infinite, it is possible to symbolically approximate trace sets using \emph{reachpipes} that compute upper and lower bounds on the evolution of the reachable sets with time. We estimate distances between corresponding sets of trajectories of two systems in terms of distances between the reachpipes. In case of two individual traces, the Skorokhod distance has been proposed as a robust and efficient notion of distance which captures both value and timing distortions. In this paper, we extend the computation of the Skorokhod distance to reachpipes, and provide algorithms to compute upper and lower bounds on the distance between two sets of traces. Our algorithms use new geometric insights that are used to compute the worst-case and best-case distances between two polyhedral sets evolving with time.
Open AccessComputing Distances between Reach Flowpipes
We investigate quantifying the difference between two hybrid dynamical systems under noise and initial-state uncertainty. While the set of traces for these systems is infinite, it is possible to symbolically approximate trace sets using \emph{reachpipes} that compute upper and lower bounds on the evolution of the reachable sets with time. We estimate distances between corresponding sets of trajectories of two systems in terms of distances between the reachpipes. In case of two individual traces, the Skorokhod distance has been proposed as a robust and efficient notion of distance which captures both value and timing distortions. In this paper, we extend the computation of the Skorokhod distance to reachpipes, and provide algorithms to compute upper and lower bounds on the distance between two sets of traces. Our algorithms use new geometric insights that are used to compute the worst-case and best-case distances between two polyhedral sets evolving with time.
- 14 July 2015
- Published by Springer Nature
- p. 234-250
Quantifying Conformance Using the Skorokhod Metric
- 14 July 2015
- Published by Springer Nature
- p. 234-250
Quantifying Conformance Using the Skorokhod Metric
- Open Access
Quantifying Conformance using the Skorokhod Metric (full version)
The conformance testing problem for dynamical systems asks, given two dynamical models (e.g., as Simulink diagrams), whether their behaviors are "close" to each other. In the semi-formal approach to conformance testing, the two systems are simulated on a large set of tests, and a metric, defined on pairs of real-valued, real-timed trajectories, is used to determine a lower bound on the distance. We show how the Skorkhod metric on continuous dynamical systems can be used as the foundation for conformance testing of complex dynamical models. The Skorokhod metric allows for both state value mismatches and timing distortions, and is thus well suited for checking conformance between idealized models of dynamical systems and their implementations. We demonstrate the robustness of the system conformance quantification by proving a \emph{transference theorem}: trajectories close under the Skorokhod metric satisfy "close" logical properties. Specifically, we show the result for the timed linear time logic \TLTL augmented with a rich class of temporal and spatial constraint predicates. We provide a window-based streaming algorithm to compute the Skorokhod metric, and use it as a basis for a conformance testing tool for Simulink. We experimentally demonstrate the effectiveness of our tool in finding discrepant behaviors on a set of control system benchmarks, including an industrial challenge problem.
Open AccessQuantifying Conformance using the Skorokhod Metric (full version)
The conformance testing problem for dynamical systems asks, given two dynamical models (e.g., as Simulink diagrams), whether their behaviors are "close" to each other. In the semi-formal approach to conformance testing, the two systems are simulated on a large set of tests, and a metric, defined on pairs of real-valued, real-timed trajectories, is used to determine a lower bound on the distance. We show how the Skorkhod metric on continuous dynamical systems can be used as the foundation for conformance testing of complex dynamical models. The Skorokhod metric allows for both state value mismatches and timing distortions, and is thus well suited for checking conformance between idealized models of dynamical systems and their implementations. We demonstrate the robustness of the system conformance quantification by proving a \emph{transference theorem}: trajectories close under the Skorokhod metric satisfy "close" logical properties. Specifically, we show the result for the timed linear time logic \TLTL augmented with a rich class of temporal and spatial constraint predicates. We provide a window-based streaming algorithm to compute the Skorokhod metric, and use it as a basis for a conformance testing tool for Simulink. We experimentally demonstrate the effectiveness of our tool in finding discrepant behaviors on a set of control system benchmarks, including an industrial challenge problem.