Search

Reaction systems (RSs) are a computational framework inspired by biochemical mechanisms. A RS defines a finite set of reactions over a finite set of entities. Typically each reaction has a local scope, because it is concerned with a small set of entities, but complex models can involve a large number of reactions and entities, and their computation can manifest unforeseen emerging behaviours. When a deviation is detected, like the unexpected production of some entities, it is often difficult to establish its causes, e.g., which entities were directly responsible or if some reaction was misconceived. Slicing is a well-known technique for debugging, which can point out the program lines containing the faulty code. In this paper, we define the first dynamic slicer for RSs and show that it can help to detect the causes of erroneous behaviour and highlight the involved reactions for a closer inspection. To fully automate the debugging process, we propose to distil monitors for starting the slicing whenever a violation from a safety specification is detected. We have integrated our slicer in BioResolve, written in Prolog which provides many useful features for the formal analysis of RSs. We define the slicing algorithm for basic RSs and then enhance it for dealing with quantitative extensions of RSs, where timed processes and linear processes can be represented. Our framework is shown at work on suitable biologically inspired RS models. [ABSTRACT FROM AUTHOR]

Contextual information plays a vital role for software developers when understanding and fixing a bug. Consequently, deep learning based program repair techniques leverage context for bug fixes. However, existing techniques treat context in an arbitrary manner, by extracting code in close proximity of the buggy statement within the enclosing file, class, or method, without any analysis to find actual relations with the bug. To reduce noise, they use a predefined maximum limit on the number of tokens to be used as context. We present a program slicing based approach, in which instead of arbitrarily including code as context, we analyze statements that have a control or data dependency on the buggy statement. We propose a novel concept called dual slicing, which leverages the context of both buggy and fixed versions of the code to capture relevant repair ingredients. We present our technique and tool called Katana, the first to apply slicing-based context for a program repair task. The results show that Katana effectively preserves sufficient information for a model to choose contextual information while reducing noise. We compare against four recent state-of-theart context-aware program repair techniques. Our results show that Katana fixes between 1.5 and 3.7 times more bugs than existing techniques. [ABSTRACT FROM AUTHOR]

Copyright of Systems Engineering & Electronics is the property of Journal of Systems Engineering & Electronics Editorial Department and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The innovation of the program slicing technique brings a revolution to address several issues (e.g. code understanding, debugging, maintenance, testing, etc.) in the more complex and large information systems. Over the past, many slicing techniques have been proposed, however, all these existing approaches did not consider the external database states. Moreover, the majority of the proposed slicing approaches are syntax-based and they do not consider the properties of variables and database attributes. Therefore, existing techniques are not directly applicable to data-intensive programs in information system scenarios and majority of them fails to compute precise slicing results. In this work, we propose a policy-based slicing framework for data-intensive programs. The policies are integrity constraints that are defined on data as per the business goal and kept in a backend database. We design our propose framework using the data dependency graph of data-intensive programs. We refine (by removing false alarms) the data dependency graph using semantics-based techniques, Condition-Action Rules and Hoare Logic. This refined graph yields precise slicing results w.r.t the policies of data-intensive programs. [ABSTRACT FROM AUTHOR]

Enterprise Architecture (EA) has been applied widely in industry as it brings substantial benefits to ease communication and improve business-IT alignment. However, due to its high complexity and cost, EA still plays a limited role in many organizations. Existing research recommends realizing more of the EA potential. EA can be developed for specific purposes, accumulated in a digital repository, and reused when needed later. Due to the diversity and inconsistency of the repository, it is challenging to find relevant EA data and reuse it. In the present research, we propose using slicing techniques to extract EA models for reuse. We validate the method with an official EA repository hosted by The Open Group. The result shows that the method could facilitate extracting existing EA model components for developing new EA artifacts to save cost, alleviate maintenance effort, and help keep the repository consistent for future (re)use. [ABSTRACT FROM AUTHOR]

Context: Petri net slicing is a technique to reduce the size of a Petri net to ease the analysis or understanding of the original Petri net. Objective: Presenting two new Petri net slicing algorithms to isolate those places and transitions of a Petri net (the slice) that may contribute tokens to one or more places given (the slicing criterion). Method: The two algorithms proposed are formalized. The maximality of the first algorithm and the minimality of the second algorithm are formally proven. Both algorithms together with three other state-of-the-art algorithms have been implemented and integrated into a single tool so that we have been able to carry out a fair empirical evaluation. Results: Besides the two new Petri net slicing algorithms, a public, free, and open-source implementation of five algorithms is reported. The results of an empirical evaluation of the new algorithms and the slices they produce are also presented. Conclusions: The first algorithm collects all places and transitions that may contribute tokens (in any computation) to the slicing criterion, while the second algorithm collects the places and transitions needed to fire the shortest transition sequence that contributes tokens to some place in the slicing criterion. Therefore, the net computed by the first algorithm can reproduce any computation that contributes tokens to any place of interest. In contrast, the second algorithm loses this possibility, but it often produces a much more reduced subnet (which still can reproduce some computations that contribute tokens to some places of interest). The first algorithm is proven maximal, and the second one is proven minimal. [ABSTRACT FROM AUTHOR]

Software fault localization is a task of isolating the statements which cause faults in a program. Fault localization is one of the monotonous, time consuming and prohibitively expensive, yet very important activities in program debugging. Manual testing and debugging is very infeasible due to the escalating scale and complexity of software systems. So, there is a strong need for automated techniques which can help developers locating bugs in programs without much human interference. This necessity has given rise to the development of a variety of fault localization techniques, each of which deals with the problem in its own way. This paper presents an overview of such techniques with some key issues and concerns relevant to software fault localization. In particular, this paper focuses on spectrum-based software fault localization (SBFL) techniques and reviews two recent approaches in detail that further improve its performance. These two approaches which are based on the concepts of Failed Execution Slice and Fault Context are evaluated experimentally on seven standard benchmark Siemens programs to compare their effectiveness against the classic Ochiai method. The experimental results show that the two approaches improve SBFL performance by an average of 27.05% and 38.64% respectively against the classic Ochiai technique. [ABSTRACT FROM AUTHOR]

We present efficient algorithms for time-sensitive control dependencies (CDs). If statement y is timesensitively control dependent on statement x, then x decides not only whether y is executed but also how many timesteps after x. If y is not standard control dependent on x, but time-sensitively control dependent, then y will always be executed after x, but the execution time between x and y varies. This allows us to discover, e.g., timing leaks in security-critical software. We systematically develop properties and algorithms for time-sensitive CDs, as well as for nontermination- sensitive CDs. These work not only for standard control flow graphs (CFGs) but also for CFGs lacking a unique exit node (e.g., reactive systems). We show that Cytron's efficient algorithm for dominance frontiers [10] can be generalized to allow efficient computation not just of classical CDs but also of time-sensitive and nontermination-sensitive CDs. We then use time-sensitive CDs and time-sensitive slicing to discover cache timing leaks in an AES implementation. Performance measurements demonstrate scalability of the approach. [ABSTRACT FROM AUTHOR]

We present efficient algorithms for time-sensitive control dependencies (CDs). If statement y is timesensitively control dependent on statement x, then x decides not only whether y is executed but also how many timesteps after x. If y is not standard control dependent on x, but time-sensitively control dependent, then y will always be executed after x, but the execution time between x and y varies. This allows us to discover, e.g., timing leaks in security-critical software. We systematically develop properties and algorithms for time-sensitive CDs, as well as for nontermination- sensitive CDs. These work not only for standard control flow graphs (CFGs) but also for CFGs lacking a unique exit node (e.g., reactive systems). We show that Cytron's efficient algorithm for dominance frontiers [10] can be generalized to allow efficient computation not just of classical CDs but also of time-sensitive and nontermination-sensitive CDs. We then use time-sensitive CDs and time-sensitive slicing to discover cache timing leaks in an AES implementation. Performance measurements demonstrate scalability of the approach. [ABSTRACT FROM AUTHOR]

A dynamic slicing algorithm is proposed in this paper along with its implementation which is dynamic for concurrent Component-oriented programs carrying multiple threads. As a part of representing the concurrent COP (CCOP) effectively, an intermediate graph is developed called Concurrent Component Dependency Graph (CCmDG). The system dependence graph (SDG) for individual components and interfaces are integrated to represent the above intermediate graph. It also consists of some new dependence edges which have been triggered for connecting the individual dependence graph of each component with the interface. Based on the graph created for the CCOP, a dynamic slicing algorithm is proposed, which sets the resultant by making the executed nodes marked during run time in Concurrent Components Dynamic Slicing (CCmDS) appropriately. For checking the competence of our algorithm, five case studies have been considered and also compared with an existing technique. From the study, we found that our algorithm results in smaller and precise size slice compared to the existing algorithm in less time. [ABSTRACT FROM AUTHOR]

Enterprise Architecture (EA) has been applied widely in industry as it brings substantial benefits to ease communication and improve business-IT alignment. However, due to its high complexity and cost, EA still plays a limited role in many organizations. Existing research recommends realizing more of the EA potential. EA can be developed for specific purposes, accumulated in a digital repository, and reused when needed later. Due to the diversity and inconsistency of the repository, it is challenging to find relevant EA data and reuse it. In the present research, we propose using slicing techniques to extract EA models for reuse. We validate the method with an official EA repository hosted by The Open Group. The result shows that the method could facilitate extracting existing EA model components for developing new EA artifacts to save cost, alleviate maintenance effort, and help keep the repository consistent for future (re)use.

Symbolic execution techniques are widely adopted in diverse fields, including software quality analysis, software defect detection and so on. Symbolic execution engines assist people to apply the technique on exploiting and test data generation conveniently. However, symbolic execution is quite hard to scale to large and complicated programs which have massive paths and conditional statements due to path explosion. Moreover, for the development cycle of software systems, the necessity to generate test data frequently and rapidly makes them tough to apply symbolic execution technique on software testing. In this paper, we propose three modes of slicing-based testability transformations to change the semantics of programs while maintaining or improving the code coverage of generated test data by the symbolic execution tool: KLEE. The concept of these testability transformations is in decreasing the execution load of KLEE through shortening execution paths in programs. Our proposed testability transformation Mode 1 (TTM1) slices programs with an automated program slicing tool and takes functions in the program as the slicing criterion. On the other hand, our proposed testability transformations Mode 2 (TTM2) and Mode 3 (TTM3) slice programs manually and limit the max depth of paths in programs to a specific value as the slicing criterion. Experimental results show TTM1 could decrease 4.5% of solver queries while increasing 6.6% of code coverage on average. TTM2 could decrease 7.7% of solver queries while increasing 5.4% of coverage on average. TTM3 could decrease 17.6% of solver queries while increasing 3.6% of coverage on average. It can be observed that though the semantics of programs change due to slicing, the coverage of test data generated by KLEE could maintain the same or even become higher. Our finding also indicates that there is room to design slicing-based testability transformations to improve quality of test generation with symbolic execution. [ABSTRACT FROM AUTHOR]

Program slicing, as a technique of program decomposition, is widely used in the field of program testing, model checking, software verification, symbolic execution, and other fields. However, the traditional approaches of program slicing tend to produce too large slices and the static program analyses are hard to be precise enough. Scenario-oriented program slicing, which considers the actual usage of software, gives a more precise perspective of program slicing. In this paper, we propose an approach of scenario-oriented program slicing, which combines constraint logic programming and program transformation. According to the observation that the output of a program transformation is a semantically equivalent program where the properties of interest are preserved, we can apply a sequence of transformations, more powerful than those needed for program specialization, refining the slicing to the desired degree of precision. And constraint logic programming has been shown to be a powerful, flexible formalism to reason about the correctness of programs. The novel contributions of this paper are as follows: 1) converting the problem of program slicing into program transformation and retrieval; 2) presenting a set of constraint handling rules for scenario-oriented program slicing in constraint logical programming programs; and 3) deriving a scenario-oriented program slicing algorithm. The method of scenario-oriented program slicing has been implemented and we have demonstrated its effectiveness and efficiency on three open source software projects in GitHub.

Statistical fault localization is an easily deployed technique for quickly determining candidates for faulty code locations. If a human programmer has to search the fault beyond the top candidate locations, though, more traditional techniques of following dependencies along dynamic slices may be better suited. In a large study of 457 bugs (369 single faults and 88 multiple faults) in 46 open source C programs, we compare the effectiveness of statistical fault localization against dynamic slicing. For single faults, we find that dynamic slicing was eight percentage points more effective than the best performing statistical debugging formula; for 66% of the bugs, dynamic slicing finds the fault earlier than the best performing statistical debugging formula. In our evaluation, dynamic slicing is more effective for programs with single fault, but statistical debugging performs better on multiple faults. Best results, however, are obtained by a hybrid approach: If programmers first examine at most the top five most suspicious locations from statistical debugging, and then switch to dynamic slices, on average, they will need to examine 15% (30 lines) of the code. These findings hold for 18 most effective statistical debugging formulas and our results are independent of the number of faults (i.e. single or multiple faults) and error type (i.e. artificial or real errors). [ABSTRACT FROM AUTHOR]

Program slicing is a technique for simplifying programs by focusing on selected aspects of their behavior. Current mainstream static slicing methods operate on dependence graph PDG (program dependence graph) or SDG (system dependence graph), but these friendly graph representations may be a bit expensive for some users. In this paper we attempt to study a light-weight approach of static program slicing, called Symbolic Program Slicing (SymPas), which works as a dataflow analysis on LLVM (low-level virtual machine). In our SymPas approach, slices are stored in symbolic forms, not in procedures being re-analyzed (cf. procedure summaries). Instead of re-analyzing a procedure multiple times to find its slices for each callling context, we calculate a single symbolic slice which can be instantiated at call sites avoiding re-analysis; SymPas is implemented with LLVM to perform slicing on LLVM intermediate representation (IR). For comparison, we systematically adapt IFDS (interprocedural finite distributive subset) analysis and the SDG-based slicing method (SDG-IFDS) to statically slice IR programs. Evaluated on open-source and benchmark programs, our backward SymPas shows a factor-of-6 reduction in time cost and a factor-of-4 reduction in space cost, compared with backward SDG-IFDS, thus being more efficient. In addition, the result shows that after studying slices from 66 programs, ranging up to 336 800 IR instructions in size, SymPas is highly size-scalable. [ABSTRACT FROM AUTHOR]

Software Traceability has been a matter of discussion in the Software Engineering community for a long time. The process of keeping and recover traces among software artifacts in any system represents a fundamental aspect to properly perform software maintenance tasks and requirements compliance verification. Furthermore, there exist application contexts where this becomes a mandatory process, for instance, banking and healthcare. Software traceability has dedicated efforts in proposing alternatives to recover lost traceability links in a coarse-grained and middle-grained detail by so far, however, proposed techniques are not enough to meet the desired levels of granularity in critical contexts. In this work we propose a fine-grained traceability algorithm designed to recover traces between high level requirements written in human natural language and source code statements where they are implemented. We tested our approach in four open-source healthcare systems to trace constraints requirements specified by the HIPAA law, and we evaluated the results as presented is this paper.

Presently, the software system has grown in size. One of the main challenges faced by programmers is to keep up with thousand or million lines of source code that needs to be read and understood. The source code is an essential resource for programmers to become familiar with the software system. Program comprehension is important in software engineering activities before performing maintenance tasks. One of the techniques that can assist the programmers in comprehending software system is known as program slicing. Program slicing is the process of extracting parts of source code programs by tracing the programs’ control and data flow related to some data item. In this paper, we conduct the literature review on program slicing in order to explore the direction of this method by focusing on various slicing techniques to provide a novel idea in program comprehension application.

Symbiotic is a bug-finding and verification tool that integrates light-weight static analyses and instrumentation with program slicing and symbolic execution. The techniques are suitably combined according to a given goal. The paper describes a particular configuration competing in Test-Comp 2019. We also provide a brief analysis of Symbiotic 's results achieved in the competition. As our tool uses a fork of the open-source symbolic executor Klee, we focus on comparison with mainstream Klee that also participated in the competition this year. [ABSTRACT FROM AUTHOR]

Ad hoc synchronizations are pervasive in multi-threaded programs. Due to their diversity and complexity, understanding the enforced synchronization relationships of ad hoc synchronizations is challenging but crucial to multi-threaded program development and maintenance. Existing techniques can partially detect primitive ad hoc synchronizations, but they cannot recognize complete implementations or infer the enforced synchronization relationships. In this paper, we propose a framework to automatically identify complex ad hoc synchronizations in full and infer their synchronization relationships. We instantiate the framework with a tool called BarrierFinder, which features various techniques, including program slicing and bounded symbolic execution, to efficiently explore the interleaving space of ad hoc synchronizations within multi-threaded programs and collect execution traces. BarrierFinder then uses these traces to characterize ad hoc synchronizations into different types with a focus on recognizing barriers. Our evaluation shows that BarrierFinder is both effective and efficient in doing this, and BarrierFinder is also helpful for programmers to understand the correctness of their implemented ad hoc synchronizations. [ABSTRACT FROM AUTHOR]

Concurrent Constraint Programming (CCP) is a declarative model for concurrency where agents interact by telling and asking constraints (pieces of information) in a shared store. Some previous works have developed (approximated) declarative debuggers for CCP languages. However, the task of debugging concurrent programs remains difficult. In this paper we define a dynamic slicer for CCP (and other language variants) and we show it to be a useful companion tool for the existing debugging techniques. We start with a partial computation (a trace) that shows the presence of bugs. Often, the quantity of information in such a trace is overwhelming, and the user gets easily lost, since she cannot focus on the sources of the bugs. Our slicer allows for marking part of the state of the computation and assists the user to eliminate most of the redundant information in order to highlight the errors. We show that this technique can be tailored to several variants of CCP, such as the timed language ntcc , linear CCP (an extension of CCPbased on linear logic where constraints can be consumed) and some extensions of CCP dealing with epistemic and spatial information. We also develop a prototypical implementation freely available for making experiments. [ABSTRACT FROM AUTHOR]

Dedicated to the memory of Sebastian Danicic. We present a theory for slicing imperative probabilistic programs containing random assignments and "observe" statements for conditioning. We represent such programs as probabilistic control-flow graphs (pCFGs) whose nodes modify probability distributions. This allows direct adaptation of standard machinery such as data dependence, postdominators, relevant variables, and so on, to the probabilistic setting. We separate the specification of slicing from its implementation: (1) first, we develop syntactic conditions that a slice must satisfy (they involve the existence of another disjoint slice such that the variables of the two slices are probabilistically independent of each other); (2) next, we prove that any such slice is semantically correct; (3) finally, we give an algorithm to compute the least slice. To generate smaller slices, we may in addition take advantage of knowledge that certain loops will terminate (almost) always. Our results carry over to the slicing of structured imperative probabilistic programs, as handled in recent work by Hur et al. For such a program, we can define its slice, which has the same "normalized" semantics as the original program; the proof of this property is based on a result proving the adequacy of the semantics of pCFGs w.r.t. the standard semantics of structured imperative probabilistic programs. [ABSTRACT FROM AUTHOR]

We present an improved version of the memory safety verification approach implemented in Symbiotic 5, the winner of the MemSafety category at the Competition on Software Verification (SV-COMP) 2018. The approach can verify programs for standard errors in memory usage like invalid pointer dereference or memory leaking. It is based on instrumentation, static pointer analysis extended to consider memory deallocations, static program slicing, and symbolic execution. The improved version brings higher precision of the extended pointer analysis and further optimizations in instrumentation. It is implemented in the current version of Symbiotic, which contains also some improvements in program slicing and symbolic execution. We explain the approach in theory, describe implementation of selected components, and provide experimental results showing the impact of particular components. [ABSTRACT FROM AUTHOR]