16 results on '"Viswanathan, Mahesh"'
Search Results
2. Model-Checking Markov Chains in the Presence of Uncertainties.
- Author
-
Hermanns, Holger, Palsberg, Jens, Sen, Koushik, Viswanathan, Mahesh, and Agha, Gul
- Abstract
We investigate the problem of model checking Interval-valued Discrete-time Markov Chains (IDTMC). IDTMCs are discrete-time finite Markov Chains for which the exact transition probabilities are not known. Instead in IDTMCs, each transition is associated with an interval in which the actual transition probability must lie. We consider two semantic interpretations for the uncertainty in the transition probabilities of an IDTMC. In the first interpretation, we think of an IDTMC as representing a (possibly uncountable) family of (classical) discrete-time Markov Chains, where each member of the family is a Markov Chain whose transition probabilities lie within the interval range given in the IDTMC. This semantic interpretation we call Uncertain Markov Chains (UMC). In the second semantics for an IDTMC, which we call Interval Markov Decision Process (IMDP), we view the uncertainty as being resolved through non-determinism. In other words, each time a state is visited, we adversarially pick a transition distribution that respects the interval constraints, and take a probabilistic step according to the chosen distribution. We show that the PCTL model checking problem for both Uncertain Markov Chain semantics and Interval Markov Decision Process semantics is decidable in PSPACE. We also prove lower bounds for these model checking problems. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
3. On Statistical Model Checking of Stochastic Systems.
- Author
-
Etessami, Kousha, Rajamani, Sriram K., Sen, Koushik, Viswanathan, Mahesh, and Agha, Gul
- Abstract
Statistical methods to model check stochastic systems have been, thus far, developed only for a sublogic of continuous stochastic logic (CSL) that does not have steady state operator and unbounded until formulas. In this paper, we present a statistical model checking algorithm that also verifies CSL formulas with unbounded untils. The algorithm is based on Monte Carlo simulation of the model and hypothesis testing of the samples, as opposed to sequential hypothesis testing. We have implemented the algorithm in a tool called VESTA, and found it to be effective in verifying several examples. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
4. Congruences for Visibly Pushdown Languages.
- Author
-
Caires, Luís, Italiano, Giuseppe F., Monteiro, Luís, Palamidessi, Catuscia, Yung, Moti, Alur, Rajeev, Kumar, Viraj, Madhusudan, P., and Viswanathan, Mahesh
- Abstract
We study congruences on words in order to characterize the class of visibly pushdown languages (Vpl), a subclass of context-free languages. For any language L, we define a natural congruence on words that resembles the syntactic congruence for regular languages, such that this congruence is of finite index if, and only if, L is a Vpl. We then study the problem of finding canonical minimal deterministic automata for Vpls. Though Vpls in general do not have unique minimal automata, we consider a subclass of VPAs called k-module single-entry VPAs that correspond to programs with recursive procedures without input parameters, and show that the class of well-matched Vpls do indeed have unique minimal k-module single-entry automata. We also give a polynomial time algorithm that minimizes such k-module single-entry VPAs. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
5. Finding Bugs in Network Protocols Using Simulation Code and Protocol-Specific Heuristics.
- Author
-
Kung-Kiu Lau, Banach, Richard, Sobeih, Ahmed, Viswanathan, Mahesh, Marinov, Darko, and Hou, Jennifer C.
- Abstract
Traditional network simulators perform well in evaluating the performance of network protocols but lack the capability of verifying the correctness of protocols. To address this problem, we have extended the J-Sim network simulator with a model checking capability that explores the state space of a network protocol to find an execution that violates a safety invariant. In this paper, we demonstrate the usefulness of this integrated tool for verification and performance evaluation by analyzing two widely used and important network protocols: AODV and directed diffusion. Our analysis discovered a previously unknown bug in the J-Sim implementation of AODV. More importantly, we also discovered a serious deficiency in directed diffusion. To enable the analysis of these fairly complex protocols, we needed to develop protocol-specific search heuristics that guide state-space exploration. We report our findings on discovering good search heuristics to analyze network protocols similar to AODV and directed diffusion. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
6. On the Complexity of Error Explanation.
- Author
-
Cousot, Radhia, Kumar, Nirman, Kumar, Viraj, and Viswanathan, Mahesh
- Abstract
When a system fails to satisfy its specification, the model checker produces an error trace (or counter-example) that demonstrates an undesirable behavior, which is then used in debugging the system. Error explanation is the task of discovering errors in the system or the reasons why the system exhibits the error trace. While there has been considerable recent interest in automating this task and developing tools based on different heuristics, there has been very little effort in characterizing the computational complexity of the problem of error explanation. In this paper, we study the complexity of two popular heuristics used in error explanation. The first approach tries to compute the smallest number of system changes that need to be made in order to ensure that the given counter-example is no longer exhibited, with the intuition being that these changes are the errors that need fixing. The second approach relies on the observation that differences between correct and faulty runs of a system shed considerable light on the sources of errors. In this approach, one tries to compute the correct trace of the system that is closest to the counter-example. We consider three commonly used abstractions to model programs and systems, namely, finite state Mealy machines, extended finite state machines and pushdown automata. We show that the first approach of trying to find the fewest program changes is NP-complete no matter which of the three formal models is used to represent the system. Moreover we show that no polynomial factor approximation algorithm for computing the smallest set of changes is possible, unless P = NP. For the second approach, we present a polynomial time algorithm that finds the closest correct trace, when the program is represented by a Mealy machine or a pushdown automata. When the program is represented by an extended finite state machine, the problem is once again NP-complete, and no polynomial factor approximation algorithm is likely. [ABSTRACT FROM AUTHOR]
- Published
- 2005
7. Using Language Inference to Verify Omega-Regular Properties.
- Author
-
Halbwachs, Nicolas, Zuck, Lenore D., Vardhan, Abhay, Sen, Koushik, Viswanathan, Mahesh, and Agha, Gul
- Abstract
A novel machine learning based approach was proposed recently as a complementary technique to the acceleration based methods for verifying infinite state systems. In this method, the set of states satisfying a fixpoint property is learnt as opposed to being iteratively computed. We extend the machine learning based approach to verifying general ω-regular properties that include both safety and liveness. To achieve this, we first develop a new fixpoint based characterization for the verification of ω-regular properties. Using this characterization, we present a general framework for verifying infinite state systems. We then instantiate our approach to the context of regular model checking where states are represented as strings over a finite alphabet and the transition relation of the system is given as a finite state transducer; unlike previous learning based algorithms, we make no assumption about the transducer being length-preserving. Using Angluin's L* algorithm for learning regular languages, we develop an algorithm for verification of ω-regular properties of such infinite state systems. The algorithm is a complete verification procedure for systems for whom the fixpoint can be represented as a regular set. We have implemented the technique in a tool called Lever and use it to analyze some examples. [ABSTRACT FROM AUTHOR]
- Published
- 2005
8. Foundations for the Run-Time Monitoring of Reactive Systems - Fundamentals of the MaC Language.
- Author
-
Zhiming Liu, Araki, Keijiro, Viswanathan, Mahesh, and Moonzoo Kim
- Abstract
As the complexity of systems grows, the correctness of systems becomes harder to achieve. This difficulty promotes a run-time monitoring technique as a promising complementary methodology for higher system assurance. To formalize and understand the computational nature of run-time monitoring is a key to utilize this valuable technique. In this paper, we formalize the notion of run-time monitoring of reactive systems in terms of ω-languages and show that the language of Monitoring and Checking (MaC) architecture, called MEDL, is expressive enough for the run-time monitoring. First, we provide a descriptive theory for the class of monitorable languages and show that this class of languages coincides with the class Π01 of the Arithmetic hierarchy. Second, we introduce a class of automata with storage that can be used to describe the class of monitorable languages using connections to the Arithmetic hierarchy. Finally, we show that MEDL can express the class of monitorable languages via the correspondence between MEDL and the automata with storage. [ABSTRACT FROM AUTHOR]
- Published
- 2005
9. Testing Extended Regular Language Membership Incrementally by Rewriting.
- Author
-
Goos, Gerhard, Hartmanis, Juris, van Leeuwen, Jan, Nieuwenhuis, Robert, Roşu, Grigore, and Viswanathan, Mahesh
- Abstract
In this paper we present lower bounds and rewriting algorithms for testing membership of a word in a regular language described by an extended regular expression. Motivated by intuitions from monitoring and testing, where the words to be tested (execution traces) are typically much longer than the size of the regular expressions (patterns or requirements), and by the fact that in many applications the traces are only available incrementally, on an event by event basis, our algorithms are based on an event-consumption idea: a just arrived event is "consumed" by the regular expression, i.e., the regular expression modifies itself into another expression discarding the event. We present an exponential space lower bound for monitoring extended regular expressions and argue that the presented rewriting-based algorithms, besides their simplicity and elegance, are practical and almost as good as one can hope. We experimented with and evaluated our algorithms in Maude. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
10. A Mori-Zwanzig and MITL Based Approach to Statistical Verification of Continuous-time Dynamical Systems**The authors acknowledge support for this work from NSF CPS grant 1329991.
- Author
-
Wang, Yu, Roohi, Nima, West, Matthew, Viswanathan, Mahesh, and Dullerud, Geir E.
- Abstract
In this work, we introduce a framework for the statistical verification of Metric Interval Temporal Logic (MITL) formulas on continuous-time dynamical systems. By considering the continuous-time Markov process associated with the dynamical system, we apply the Mori-Zwanzig method to reduce the original system to a Continuous-Time Markov Chain (CTMC). Accordingly, the MITL formulas on the original system can be reduced to MITL formulas on the CTMC. Furthermore, we propose a statistical verification algorithm for checking the MITL formulas on the CTMCand show that the original MITL formulas on the original system can be checked by this procedure.
- Published
- 2015
- Full Text
- View/download PDF
11. Java-MaC: A Run-Time Assurance Approach for Java Programs
- Author
-
Kim, MoonZoo, Viswanathan, Mahesh, Kannan, Sampath, Lee, Insup, and Sokolsky, Oleg
- Abstract
We describe Java-MaC, a prototype implementation of the Monitoring and Checking (MaC) architecture for Java programs. The MaC architecture provides assurance that the target program is running correctly with respect to a formal requirements specification by monitoring and checking the execution of the target program at run-time. MaC bridges the gap between formal verification, which ensures the correctness of a design rather than an implementation, and testing, which does not provide formal guarantees about the correctness of the system. Use of formal requirement specifications in run-time monitoring and checking is the salient aspect of the MaC architecture. MaC is a lightweight formal method solution which works as a viable complement to the current heavyweight formal methods. In addition, analysis processes of the architecture including instrumentation of the target program, monitoring, and checking are performed fully automatically without human direction, which increases the accuracy of the analysis. Another important feature of the architecture is the clear separation between monitoring implementation-dependent low-level behaviors and checking high-level behaviors, which allows the reuse of a high-level requirement specification even when the target program implementation changes. Furthermore, this separation makes the architecture modular and allows the flexibility of incorporating third party tools into the architecture. The paper presents an overview of the MaC architecture and a prototype implementation Java-MaC.
- Published
- 2004
- Full Text
- View/download PDF
12. Computational Analysis of Run-time Monitoring: Fundamentals of Java-MaC.
- Author
-
Kim, Moonjoo, Kannan, Sampath, Lee, Insup, Sokolsky, Oleg, and Viswanathan, Mahesh
- Subjects
JAVA programming language ,PROGRAMMING languages ,COMPUTATIONAL complexity ,ELECTRONIC data processing - Abstract
A run-time monitor shares computational resources, such as memory and CPU time, with the target program. Furthermore, heavy computation performed by a monitor for checking target program''s execution with respect to requirement properties can be a bottleneck to the target program''s execution. Therefore, computational characteristics of run-time monitoring cause a significant impact on the target program''s execution.We investigate computational issues on run-time monitoring. The first issue is the power of run-time monitoring. In other words, we study the class of properties run-time monitoring can evaluate. The second issue is computational complexity of evaluating properties written in process algebraic language. Third, we discuss sound abstraction of the target program''s execution, which does not change the result of property evaluation. This abstraction can be used as a technique to reduce monitoring overhead. Theoretical understanding obtained from these issues affects the implementation of Java-MaC, a toolset for the run-time monitoring and checking of Java programs. Finally, we demonstrate the abstraction-based overhead reduction technique implemented in Java-MaC through a case study. [Copyright &y& Elsevier]
- Published
- 2002
- Full Text
- View/download PDF
13. Verisim
- Author
-
Bhargavan, Karthikeyan, Gunter, Carl A., Kim, Moonjoo, Lee, Insup, Obradovic, Davor, Sokolsky, Oleg, and Viswanathan, Mahesh
- Published
- 2000
- Full Text
- View/download PDF
14. Spot-Checkers
- Author
-
Ergün, Funda, Kannan, Sampath, Kumar, S.Ravi, Rubinfeld, Ronitt, and Viswanathan, Mahesh
- Abstract
On Labor Day weekend, the highway patrol sets up spot-checks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very similar idea in the context of program checking to ascertain with minimal overhead that a program output is reasonablycorrect. Our model of spot-checkingrequires that the spot-checker must run asymptotically much faster than the combined length of the input and output. We then show that the spot-checking model can be applied to problems in a wide range of areas, including problems regarding graphs, sets, and algebra. In particular, we present spot-checkers for sorting, convex hull, element distinctness, set containment, set equality, total orders, and correctness of group and field operations. All of our spot-checkers are very simple to state and rely on testing that the input and/or output have certain simple properties that depend on very few bits. Our results also give property tests as defined by Rubinfeld and Sudan (1996, SIAM J. Comput.25, 252–271), Rubinfeld (1994, “Proc. 35th Foundations of Computer Science,” pp. 288–299), and Goldreich et al.(1998, J. Assoc. Comput. Mach.45, 653–750).
- Published
- 2000
- Full Text
- View/download PDF
15. Multimedia document retrieval using speech and speaker recognition
- Author
-
Viswanathan, Mahesh, Beigi, Homayoon S.M., Dharanipragada, Satya, Maali, Fereydoun, and Tritschler, Alain
- Abstract
Speech and speaker recognition systems are rapidly being deployed in real-world applications. In this paper, we discuss the details of a system and its components for indexing and retrieving multimedia content derived from broadcast news sources. The audio analysis component calls for real-time speech recognition for converting the audio to text and concurrent speaker analysis consisting of the segmentation of audio into acoustically homogeneous sections followed by speaker identification. The output of these two simultaneous processes is used to abstract statistics to automatically build indexes for text-based and speaker-based retrieval without user intervention. The real power of multimedia document processing is the possibility of Boolean queries in the form of combined text- and speaker-based user queries. Retrieval for such queries entails combining the results of individual text and speaker based searches. The underlying techniques discussed here can easily be extended to other speech-centric applications and transactions.
- Published
- 2000
- Full Text
- View/download PDF
16. Tools for a Document Image Utility
- Author
-
Krishnamoorthy, M., Molholt, Patricia, Nagy, George, Seth, Sharad, and Viswanathan, Mahesh
- Published
- 1993
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.