mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Demand-Driven Static Backward Program Slicing Based on Predicated Code Block Graphs
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. (Programming Languages)ORCID iD: 0000-0001-9410-1344
2019 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Static backward program slicing is a technique to compute the set of program statements, predicates and inputs that might affect the value of a particular variable at a program location. The importance of this technique comes from being an essential part of many critical areas such as program maintenance, testing, verification, debugging, among others. The state-of-art slicing approach collects all the data- and control-flow information in the source code before the slicing, but not all the collected information are used for computing the slice. Thus, this approach causes a significant amount of unnecessary computations, particularly for slicing large industrial systems, where unnecessary computations lead to wastage of a considerable amount of processing time and memory. Moreover, this approach often suffers from scalability issues.

The demand-driven slicing approaches aim at solving this problem by avoiding unnecessary computations. However, some of these approaches trade precision for performance, whereas others are not entirely demand-driven, particularly for addressing unstructured programs, pointer analysis, or inter-procedural cases.

This thesis presents a new demand-driven slicing approach that addresses well-structured, unstructured, and inter-procedural programs. This approach has four distinct features, each of which prevents a special type of unnececessary computations. The effectiveness and correctness of the proposed approach are verified using experimental evaluation. In addition, the thesis proposes an approach that can compute on the fly the control dependencies in unstructured programs.

Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2019.
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 284
Keywords [en]
Static Program Analysis, Static Program Slicing, Control Dependency
National Category
Embedded Systems
Identifiers
URN: urn:nbn:se:mdh:diva-45229ISBN: 978-91-7485-440-4 (print)OAI: oai:DiVA.org:mdh-45229DiVA, id: diva2:1351759
Presentation
2019-11-27, Gamma, Mälardalens högskola, Västerås, 13:15 (English)
Opponent
Supervisors
Funder
Knowledge FoundationVinnovaSwedish Foundation for Strategic Research Available from: 2019-09-19 Created: 2019-09-16 Last updated: 2019-10-07Bibliographically approved
List of papers
1. Static backward program slicing for safety-critical systems
Open this publication in new window or tab >>Static backward program slicing for safety-critical systems
2015 (English)In: Lecture Notes in Computer Science, 2015, p. 50-65Conference paper, Published paper (Refereed)
Abstract [en]

Static program slicing is a technique to detect the program parts (i.e. the “slice”) of the given program possibly affecting a given property. The technique is of interest for analysing safety-critical software, since it can identify the program parts that may affect various safety properties. Verification efforts can then be directed towards those parts, leading to a more efficient verification process. We have developed a novel method for static backward program slicing. The method works for well-structured programs, as commonly demanded by coding standards for safety-critical software. It utilises the program structure to obtain a highly efficient slicing process, where control dependencies are inferred from the program structure, and the slicing is done on-the-fly concurrently with the data dependence analysis. We have evaluated our method experimentally. For applications that require few slices to be taken, like checking for a set of safety properties, we obtain large speedups as compared with the standard method for static backward program slicing. We have also investigated how the speedup varies with various parameters such as code size, size of the slice relative to the full program, and relative frequency of conditions in the code.

Keywords
Dataflow analysis, Program dependency graph, Program slicing, Strongly live variable, Ada (programming language), Codes (symbols), Data flow analysis, Program processors, Safety engineering, Data dependence analysis, Program dependency graphs, Relative frequencies, Safety critical software, Safety critical systems, Verification process, Application programs
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:mdh:diva-29840 (URN)10.1007/978-3-319-19584-1_4 (DOI)2-s2.0-84947918293 (Scopus ID)9783319195834 (ISBN)
Conference
20th Ada-Europe International Conference on Reliable Software Technologies, Ada-Europe 2015; Madrid; Spain; 22 June 2015 through 26 June 2015
Available from: 2015-12-04 Created: 2015-12-04 Last updated: 2019-09-17Bibliographically approved
2. Enhanced PCB Based Slicing
Open this publication in new window or tab >>Enhanced PCB Based Slicing
2016 (English)In: Proceedings of the Fifth International Valentin Turchin Workshop on Metacomputation, Pereslavl-Zalessky, Russian Federation, 2016, p. 71-91Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Pereslavl-Zalessky, Russian Federation: , 2016
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:mdh:diva-33770 (URN)
Conference
Fifth International Valentin Turchin Workshop on Metacomputation META 2016 , 27 Jun 2016, Pereslavl-Zalessky, Russian Federation
Projects
SYNOPSIS - Safety Analysis for Predictable Software Intensive Systems
Available from: 2016-11-21 Created: 2016-11-21 Last updated: 2019-09-17Bibliographically approved
3. Demand-Driven Static Backward Slicing for Unstructured Programs
Open this publication in new window or tab >>Demand-Driven Static Backward Slicing for Unstructured Programs
2019 (English)Report (Other academic)
Abstract [en]

Backward program slicing identifies the program parts that might influence a particular variable at a program point. A program part (e.g., a statement) can be directly influenced by another part due to its data or control dependence on the later. The classical program slicing approaches are designed to find in advance all the data and control dependencies in the program. This design entails a considerable amount of unnecessary computations because not all the dependencies are required for computing the slice. Demand-driven program slicing approaches try to raise the analysis performance by avoiding the unnecessary computations. However, these approaches cannot address unstructured programs in a demand-driven fashion. On the other hand, the existing techniques that compute the control dependencies in unstructured programs are based on fixed-point iterations, which limits their integration to the demand-driven slicing approaches. Program slicing based on Predicate Code Block (PCB) is a new demand-driven slicing approach that can address only structured programs. This paper presents the first demand-driven technique to compute the control dependencies in unstructured programs. In this regard, the technique uses flow information, location-based information and syntactic structure of the source code. Further, the paper shows how the new technique can be integrated to the PCB-based slicing approach to address unstructured programs.

Keywords
Static Program AnalysisPredicate Control BlockControl DependenceStatic Program SlicingUnstructured Programs.
National Category
Engineering and Technology Computer Systems
Identifiers
urn:nbn:se:mdh:diva-45033 (URN)MDH-MRTC-324/2019-1-SE (ISRN)
Projects
TESTOMAT Project - The Next Level of Test Automation
Available from: 2019-08-22 Created: 2019-08-22 Last updated: 2019-09-17Bibliographically approved

Open Access in DiVA

The full text will be freely available from 2019-11-06 08:00
Available from 2019-11-06 08:00

Authority records BETA

Khanfar, Husni

Search in DiVA

By author/editor
Khanfar, Husni
By organisation
Embedded Systems
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 51 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf