Master of Science, Miami University, 2017, Computer Science and Software Engineering

Several approaches have been suggested for computing program slices based on different perspectives, including forward slicing, backward slicing, static slicing, and dynamic slicing. The applications of slicing are numerous, including testing, effort estimation, and impact analysis. Surprisingly, given the maturity of slicing, few approaches exist for visualizing slices. Here we present our research for visualizing large systems based on program slicing. In particular, we use treemaps to facilitate hierarchical, slicing-based navigation, we use bipartite graphs to facilitate visual impact analysis over a given variable or line of code, parallel coordinates to facilitate visual impact analysis over code blocks or variable groupings, and a text-based code browser to provide detailed context for the relevant visualizations. We believe our tools support various software maintenance tasks, including providing analysts an interactive visualization of the impact of potential changes, thus allowing developers to plan maintenance accordingly. We evaluate the research by assessing usability through a think aloud protocol and a heuristic evaluation. Our results indicate users could effectively complete the evaluation tasks we provided, and the visual idioms utilized in vizSlice were effective at communicating the underlying data to them. However, controls for these visualizations need improvement in both affordance and visibility. Regardless of any difficulties users experienced with vizSlice, users consistently rated the system positively on the measured heuristics. We provide insights on these results, future plans for improving vizSlice, and provide guidance for future research on visualizing program slices.

Committee: Gerald Gannod (Advisor); Hakam Alomari (Committee Member); Matthew Stephan (Committee Member); James Kiper (Committee Member) Subjects: Computer Science

Master of Computer Science, Miami University, 2012, Computer Science and Software Engineering

Digital evolution is a form of evolutionary computation closely associated with artificial life in which a population of self-replicating computer programs that are subject to mutations and natural selection exists in a user-defined computational environment. Each organism comprises an evolved genome (program) of assembly-like instructions and a virtual CPU on which the genome executes. Since each genome is produced by a sequence of random mutations over evolutionary time, the encoding of behavior within the genome is often obscure, making manual analysis tedious and time-consuming. In this thesis, we present a methodology for analyzing digital organisms using program understanding and Bioinformatics techniques, including program slicing and sequence alignment, both of which we have adapted for the digital evolution context. We apply this approach to a set of evolved genomes and demonstrate how dependency analysis and slicing facilitate identification of known patterns and operations embedded within the genomes.

Committee: Jerry Gannod PhD (Advisor); John Karro PhD (Other); James Kiper PhD (Other) Subjects: Computer Science

Master of Science (MS), Bowling Green State University, 2018, Computer Science

Many programming languages contain a way to provide a sub-portion of the source code that performs a specific and often independent behavior. Depending on the language this is called a (sub-)routine, method, function, procedure, etc. One of the main purposes of creating a routine is to enable re-use. As devised, routines are intended to be called from multiple places within a program. Sometimes, however, the same code is repeated within a project or across projects. In this work, we investigate how often such routines are repeated in a large-scale corpus of open source software. This work attempts to independently reproduce a prior research result by Nguyen et al., building from the ground up the analysis framework and analyzing a different and very large set of open source software projects. In this work, we use the Boa infrastructure to investigate routine repetitiveness by analyzing over 300k open source projects from GitHub. Similar to the prior work, we first compute the program dependence graphs (PDGs) for each routine in the dataset, perform normalization on the PDGs, and look for repetitions both within and across projects. Our experiment shows that about 16.4% of routines repeat within a project and approximately 11% of routines repeat across at least two different projects. We then perform static program slicing on the PDGs, slicing the graph on each routine argument to obtain subroutines and look for repetitiveness once again. We observe that approximately 17% of all subroutines repeat within a project and 11% repeat across projects. Finally, we investigate if the size of the PDG or the number of control nodes has any impact on the repetitiveness of routines. Overall, our results confirm the trends shown in the prior study, though with differences in the size of the results.

Committee: Robert Dyer Dr. (Advisor); Robert Green Dr. (Committee Member); Raymon Kresman Dr. (Committee Member) Subjects: Computer Science

PHD, Kent State University, 2012, College of Arts and Sciences / Department of Computer Science

The dissertation introduces an efficient and highly scalable lightweight forward static slicing approach. The implementation of the approach is applied, in novel ways, to large-scale software systems. Program slicing is a commonly used approach for understanding and detecting the impact of changes to software. That is, given a variable and the location of that variable in a program, the other parts of the program that are affected by this variable can be determined. The approach has been used successfully for many years for various maintenance tasks. For example, slicing was used to help address the Y2K problem by identifying parts of a program that could be impacted by changes on date fields. However, current approaches to program slicing are based on computing the program dependency graph (PDG) and computing the PDG can be very computationally expensive and scales poorly. Additionally, current approaches assume the system being examined can be completely compiled. This is not always the case when a system is undergoing maintenance, in particular during a platform change. The approach taken here does not compute the complete PDG, instead it determines program dependencies locally as needed when computing a slice for a give variable. Due to the efficient nature of the approach it is used to address a number of applications and problems that, in practice cannot be (or are extremely costly) to address with current heavyweight slicing approaches. The dissertation addresses the following specific problems in novel ways. The scalability of the approach is demonstrated for large-scale systems, specifically all the slices for 17 years of versions of the Linux kernel (over 900 versions) is performed. The tool is highly scalable and can generate the slices for all variables of the Linux kernel in less than 15 minutes. How slices change over the history of software system is investigated and slice-based software metrics are introduced that reflect maintenance effort. These m (open full item for complete abstract)

Committee: Jonathan Maletic PhD (Advisor); Feodor Dragan PhD (Committee Member); Ruoming Jin PhD (Committee Member); Michael Collard PhD (Committee Member); John Portman PhD (Committee Member); Eugene Gartland PhD (Committee Chair) Subjects: Computer Science

Doctor of Philosophy, Case Western Reserve University, 2007, Computer Engineering

Modern complex digital systems are described in Hardware Description Language (HDL). The increase in design complexity is causing verification tools to require large amount of resources. In this research, we present a program slicing technique to extract statements from an RTL design that directly or indirectly contribute to a formal verification rule. The extracted statements constitute a less complex design that reduces the resource needed by verification tools without compromising the quality of the result. Both static and conditioned Verilog slicer is implemented in a computer program that is used as a pre-processor to SAT-based bounded model checker SMV and ATPG-based bounded model checker Formal. We show experimentally that the resources of the formal verification tool in terms of both CPU and memory are reduced significantly when verifying the USB2.0 IP core. The proposed slicer is the first hardware slicing technique that handles inter-module signal dependency in a hierarchical Verilog design environment.

Committee: Daniel Saab (Advisor) Subjects: