Bangalore, India
Bangalore, India

Time filter

Source Type

Kodali A.,University of Connecticut | Singh S.,University of Connecticut | Pattipati K.,GM India Science Laboratory
IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans | Year: 2013

The set-covering problem is widely used to model many real-world applications. In this paper, we formulate a generalization of set-covering, termed dynamic set-covering (DSC), which involves a series of coupled set-covering problems over time. We motivate the DSC problem from the viewpoint of a dynamic multiple fault diagnosis problem, wherein faults, possibly intermittent, evolve over time; the fault-test dependencies are deterministic (components associated with passed tests cannot be suspected to be faulty and at least one of the components associated with failed tests is faulty), and the test outcomes may be observed with delay. The objective of the DSC problem is to infer the most probable time sequence of a parsimonious set of failure sources that explains the observed test outcomes over time. The DSC problem is NP-hard and intractable due to the fault-test dependency matrix that couples the failed tests and faults via the constraint matrix, and the temporal dependence of failure sources over time. By relaxing the coupling constraints using Lagrange multipliers, the DSC problem can be decoupled into independent subproblems, one for each fault. Each subproblem is solved using the Viterbi decoding algorithm, and a primal feasible solution is constructed by modifying the Viterbi solutions via a heuristic. The Lagrange multipliers are updated using a subgradient method. The proposed Viterbi-Lagrangian relaxation algorithm provides a measure of suboptimality via an approximate duality gap. As a major practical extension of the above problem, we also consider the problem of diagnosing faults with delayed test outcomes, termed delay DSC. A detailed experimental evaluation of the algorithms is provided using real-world problems that exhibit masking faults. © 2013 IEEE.

Kodali A.,University of Connecticut | Pattipati K.,University of Connecticut | Singh S.,GM India Science Laboratory
IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans | Year: 2013

In this paper, we formulate a coupled factorial hidden Markov model-based (CFHMM) framework to diagnose dependent faults occurring over time (dynamic case). In our previous research, the problem of diagnosing multiple faults over time (dynamic multiple fault diagnosis (DMFD)) is solved based on a sequence of test outcomes by assuming that the faults and their time evolution are independent. This problem is NP-hard, and, consequently, we developed a polynomial approximation algorithm using Lagrangian relaxation within a FHMM framework. Here, we extend this formulation to a mixed memory Markov coupling model, termed dynamic coupled fault diagnosis (DCFD) problem, to determine the most likely sequence of (dependent) fault states, the one that best explains the observed test outcomes over time. An iterative Gauss-Seidel coordinate ascent optimization method is proposed for solving the DCFD problem. A soft Viterbi algorithm is also implemented within the framework for decoding-dependent fault states over time. We demonstrate the algorithm on simulated systems with coupled faults and the results show that this approach improves the correct isolation rate (CI) as compared to the formulation where independent fault states (DMFD) are assumed. As a by-product, we show empirically that, while diagnosing for independent faults, the DMFD algorithm based on block coordinate ascentmethod, although it does not provide a measure of suboptimality, provides better primal cost and higher CI than the Lagrangian relaxation method for independent fault case. Two real-world examples (a hybrid electric vehicle, and a mobile autonomous robot) with coupled faults are also used to evaluate the proposed framework. © 2013 IEEE.

Biswas S.,Indian Institute of Technology Kharagpur | Mall R.,Indian Institute of Technology Kharagpur | Satpathy M.,GM India Science Laboratory
IEEE Embedded Systems Letters | Year: 2011

Execution dependencies arise among the tasks of an embedded program due to issues such as task priority, task precedence, and intertask communication. We argue that execution dependencies among tasks need to be suitably considered in various embedded software engineering activities such as debugging, regression testing, and computation of complexity metrics. In this letter, we discuss how task execution dependencies among real-time tasks can be identified from static code analysis. Subsequently, we briefly describe an application of our analysis to regression test selection. © 2009 IEEE.

Biswas S.,Indian Institute of Technology Kharagpur | Mall R.,Indian Institute of Technology Kharagpur | Satpathy M.,GM India Science Laboratory | Sukumaran S.,GM India Science Laboratory
Informatica (Ljubljana) | Year: 2011

Regression testing is an important and expensive activity that is undertaken every time a program is modified to ensure that the modifications do not introduce new bugs into previously validated code. An important research problem, in this context, is the selection of a relevant subset of test cases from the initial test suite that would minimize both the regression testing time and effort without sacrificing the thoroughness of regression testing. Researchers have proposed a number of regression test selection techniques for different programming paradigms such as procedural, object-oriented, component-based, database, aspect, and web applications. In this paper, we review the important regression test selection techniques proposed for various categories of programs and identify the emerging trends.

Vulimiri A.,Indian Institute of Technology Kharagpur | Gupta A.,Indian Institute of Technology Kharagpur | Roy P.,Indian Institute of Technology Kharagpur | Muthaiah S.N.,GM India Science Laboratory | Kherani A.A.,GM India Science Laboratory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2010

Safety applications designed for Vehicular Ad Hoc Networks (VANETs) can be compromised by participating vehicles transmitting false or inaccurate information. Design of mechanisms that detect such misbehaving nodes is an important problem in VANETs. In this paper, we investigate the use of correlated information, called "secondary alerts", generated in response to another alert, called as the "primary alert" to verify the truth or falsity of the primary alert received by a vehicle. We first propose a framework to model how such correlated secondary information observed from more than one source can be integrated to generate a "degree of belief" for the primary alert. We then show an instantiation of the model proposed for the specific case of Post-Crash Notification as the primary alert and Slow/Stopped Vehicle Advisory as the secondary alerts. Finally, we present the design and evaluation of a misbehavior detection scheme (MDS) for PCN application using such correlated information to illustrate that such information can be used efficiently for MDS design. © 2010 Springer-Verlag.

Suman R.R.,Indian Institute of Technology Kharagpur | Mall R.,Indian Institute of Technology Kharagpur | Sukumaran S.,GM India Science Laboratory | Satpathy M.,GM India Science Laboratory
Journal of Object Technology | Year: 2010

We propose a novel black-box approach to reverse engineer the state model of software components. We assume that in dierent states, a component supports dierent subsets of its services and that the state of the component changes solely due to invocation of its services. To construct the state model of a component, we track the changes (if any) to its supported services that occur after invoking various services. Case studies carried out by us show that our approach generates state models with sucient accuracy and completeness for components with services that either require no input data parameters or require parameters with small set of values. © JOT, 2008.

Biswas S.,Indian Institute of Technology Kharagpur | Mall R.,Indian Institute of Technology Kharagpur | Satpathy M.,GM India Science Laboratory
Transactions on Embedded Computing Systems | Year: 2013

The current approaches for regression test selection of embedded programs are usually based on dataand control-dependency analyses, often augmented with human reasoning. Existing techniques do not take into account additional execution dependencies which may exist among code elements in such programs due to features such as tasks, task deadlines, task precedences, and intertask communications. In this context, we propose a model-based regression test selection technique for such programs. Our technique first constructs a graph model of the program; the proposed graph model has been designed to capture several characteristics of embedded programs, such as task precedence order, priority, intertask communication, timers, exceptions and interrupt handlers, which we consider important for regression-test selection. Our regression test selection technique selects test cases based on an analysis of the constructed graph model. We have implemented our technique to realize a prototype tool. The experimental results obtained using this tool show that, on average, our approach selects about 28.33% more regression test cases than those selected by a traditional approach. We observed that, on average, 36.36% of the fault-revealing test cases were overlooked by the existing regression test selection technique. © 2013 ACM.

Loading GM India Science Laboratory collaborators
Loading GM India Science Laboratory collaborators