Kannan, Sampath
Email Address
ORCID
Disciplines
relationships.isProjectOf
relationships.isOrgUnitOf
Position
Introduction
Research Interests
Collection
36 results
Search Results
Now showing 1 - 10 of 36
Publication A Retrospective Look at the Monitoring and Checking (MaC) Framework(2019-10-01) Kannan, Sampath; Lee, Insup; Sokolsky, Oleg; Kim, Moonzoo; Viswanathan, MaheshThe Monitoring and Checking (MaC) project gave rise to a framework for runtime monitoring with respect to formally specified properties, which later came to be known as runtime verification. The project also built a pioneering runtime verification tool, Java-MaC, that was an instantiation of the approach to check properties of Java programs. In this retrospective, we discuss decisions made in the design of the framework and summarize lessons learned in the course of the project.Publication Algorithms for the Generalized Sorting Problem(2011-10-01) Kannan, Sampath; Huang, Zhiyi; Khanna, SanjeevWe study the generalized sorting problem where we are given a set of n elements to be sorted but only a subset of all possible pairwise element comparisons is allowed. The goal is to determine the sorted order using the smallest possible number of allowed comparisons. The generalized sorting problem may be equivalently viewed as follows. Given an undirected graph G(V,E) where V is the set of elements to be sorted and E defines the set of allowed comparisons, adaptively find the smallest subset E' E of edges to probe such that the directed graph induced by E' contains a Hamiltonian path. When G is a complete graph, we get the standard sorting problem, and it is well-known that Θ(n log n) comparisons are necessary and sufficient. An extensively studied special case of the generalized sorting problem is the nuts and bolts problem where the allowed comparison graph is a complete bipartite graph between two equal-size sets. It is known that for this special case also, there is a deterministic algorithm that sorts using Θ(n log n) comparisons. However, when the allowed comparison graph is arbitrary, to our knowledge, no bound better than the trivial O(n2) bound is known. Our main result is a randomized algorithm that sorts any allowed comparison graph using Õ(n3⁄2) comparisons with high probability (provided the input is sortable). We also study the sorting problem in randomly generated allowed comparison graphs, and show that when the edge probability is p, Õ(min{n/p2 , n3⁄2p √p}) comparisons suffice on average to sort.Publication Reconstructing Strings from Random Traces(2004-01-11) Kannan, Sampath; Batu, Tugkan; Khanna, Sanjeev; McGregor, AndrewWe are given a collection of m random subsequences (traces) of a string t of length n where each trace is obtained by deleting each bit in the string with probability q. Our goal is to exactly reconstruct the string t from these observed traces. We initiate here a study of deletion rates for which we can successfully reconstruct the original string using a small number of samples. We investigate a simple reconstruction algorithm called Bitwise Majority Alignment that uses majority voting (with suitable shifts) to determine each bit of the original string. We show that for random strings t, we can reconstruct the original string (w.h.p.) for q = O(1/ log n) using only O(log n) samples. For arbitrary strings t, we show that a simple modification of Bitwise Majority Alignment reconstructs a string that has identical structure to the original string (w.h.p.) for q = O(1/n1/2+ε) using O(1) samples. In this case, using O(n log n) samples, we can reconstruct the original string exactly. Our setting can be viewed as the study of an idealized biological evolutionary process where the only possible mutations are random deletions. Our goal is to understand at what mutation rates, a small number of observed samples can be correctly aligned to reconstruct the parent string. In the process of establishing these results, we show that Bitwise Majority Alignment has an interesting selfcorrecting property whereby local distortions in the traces do not generate errors in the reconstruction and eventually get corrected.Publication QuanTM: A Quantitative Trust Management System(2009-03-01) West, Andrew G; Aviv, Adam J; Chang, Jian; Prabhu, Vinayak S; Blaze, Matthew A; Kannan, Sampath; Lee, Insup; Smith, Jonathan M; Sokolsky, OlegQuantitative Trust Management (QTM) provides a dynamic interpretation of authorization policies for access control decisions based on upon evolving reputations of the entities involved. QuanTM, a QTM system, selectively combines elements from trust management and reputation management to create a novel method for policy evaluation. Trust management, while effective in managing access with delegated credentials (as in PolicyMaker and KeyNote), needs greater flexibility in handling situations of partial trust. Reputation management provides a means to quantify trust, but lacks delegation and policy enforcement. This paper reports on QuanTM’s design decisions and novel policy evaluation procedure. A representation of quantified trust relationships, the trust dependency graph, and a sample QuanTM application specific to the KeyNote trust management language, are also proposed.Publication Simulation-Based Graph Similarity(2006-03-27) Sokolsky, Oleg; Kannan, Sampath; Lee, InsupWe present symmetric and asymmetric similarity measures for labeled directed rooted graphs that are inspired by the simulation and bisimulation relations on labeled transition systems. Computation of the similarity measures has close connections to discounted Markov decision processes in the asymmetric case and to perfect-information stochastic games in the symmetric case. For the symmetric case, we also give a polynomial-time algorithm that approximates the similarity to any desired precision.Publication Computational Analysis of Run-time Monitoring: Fundamentals of Java-MaC(2002-07-26) Kannan, Sampath; Lee, Insup; Kim, Moonjoo; Sokolsky, Oleg; Viswanathan, MaheshA 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.Publication Optimal Control of Software Ensuring Safety and Functionality(2005-10-11) Kannan, Sampath; Easwaran, Arvind; Lee, InsupExisting verification and validation methodologies can detect software violations very effectively but fail to provide any mechanism for correcting faults once they are detected. Detection of faults, their diagnosis and corrective actions are all essential components of any software rectification framework. In this paper, we propose a framework for correction of violations in software systems ensuring that the desired goals of the system are achieved. We describe a stochastic finite state machine used to abstract a software system along with the uncertainty in its operating environment. Safety property violations and satisfaction of functionalities are abstracted using penalties and rewards on the states, respectively. Rectification of software is then formulated as a stochastic optimal control problem over this abstraction. Algorithms polynomial in the size of the abstraction have been developed for solving this optimization problem exactly. The paper also applies the developed framework to a variety of examples from different domains.Publication Randomized Pursuit-Evasion with Local Visibility(2006-02-15) Kannan, Sampath; Isler, Volkan; Khanna, SanjeevWe study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the hunters but it can see them only if they are located on adjacent nodes. We show that two hunters suffice for catching rabbits with such local visibility with high probability. We distinguish between reactive rabbits who move only when a hunter is visible and general rabbits who can employ more sophisticated strategies. We present polynomial time algorithms that decide whether a graph G is hunter-win, that is, if a single hunter can capture a rabbit of either kind on G.Publication Spatio-Temporal Analysis of Wikipedia Metadata and the STiki Anti-Vandalism Tool(2010-07-01) West, Andrew G.; Kannan, Sampath; Lee, InsupThe bulk of Wikipedia anti-vandalism tools require natural language processing over the article or diff text. However, our prior work demonstrated the feasibility of using spatio-temporal properties to locate malicious edits. STiki is a real-time, on-Wikipedia tool leveraging this technique. The associated poster reviews STiki's methodology and performance. We find competing anti-vandalism tools inhibit maximal performance. However, the tool proves particularly adept at mitigating long-term embedded vandalism. Further, its robust and language-independent nature make it well-suited for use in less-patrolled Wiki installations.Publication VC-Dimension of Exterior Visibility(2004-05-01) Kannan, Sampath K; Isler, Volkan; Daniilidis, Kostas; Valtr, PavelIn this paper, we study the Vapnik-Chervonenkis (VC)-dimension of set systems arising in 2D polygonal and 3D polyhedral configurations where a subset consists of all points visible from one camera. In the past, it has been shown that the VC-dimension of planar visibility systems is bounded by 23 if the cameras are allowed to be anywhere inside a polygon without holes [1]. Here, we consider the case of exterior visibility, where the cameras lie on a constrained area outside the polygon and have to observe the entire boundary. We present results for the cases of cameras lying on a circle containing a polygon (VC-dimension= 2) or lying outside the convex hull of a polygon (VC-dimension= 5). The main result of this paper concerns the 3D case: We prove that the VC-dimension is unbounded if the cameras lie on a sphere containing the polyhedron, hence the term exterior visibility.