"Model Analysis" 2010/2011


Dr. Günter Kniesel, Daniel Speicher, Jan Nonnen

Lab Phase

  • Date: Mo 11.10.2010 to Mo 31.01.2011 (each Monday, from first to last course week of winter semester)
  • Time: 13:00-18:00

Technologies

  • Prolog / JTransformer: for implementing analyses
  • CTs: for generating abstractions that represent analysis results
  • StarTransformer: for defining meta models of the analysis results that let us browse the results visually like any other factbase
  • GIT: version management
  • HUDSON: continous integration
  • JIRA: issue management
  • MYLYN: task focused user interface for Eclipse
  • ECLIPSE: development environment

Format

  • 14 Participants
    • 6 from ALP lecture
    • 5 from MoSA seminar
    • 2 course instructors (DSP & GK)
    • 1 supervising tutor (JN)
  • Agile software development techniques
    • Joint start with “stand up meeting”
    • On demand presentations
    • Fixed Iteration Length
    • Agile Planing Game
    • Pair Programming
    • Pair Switching
    • Refactoring
    • Testing

Topics

During the lab phase we will leverage our conceptual knowledge from the seminar phase to design, implement, evaluate and document solutions to the issues sketched below.

The prioritization and scheduling of the issues (some could be addressed in parallel by different subgroups) will be decided jointly during the lab. We will do this in the form of the ”planing game” of extreme programming, which will be introduced on the fly.

Graph Algorithms

  • Problem: The type, data and control flow analyzes largely operate on graphs. Therefore, fast and reliable Prolog implementations of several essential graph algorithms will be an indispensable basis for the entire lab.
  • Starting point: Strongly connected components (code by GK)
  • Aim:
    • Shortest / longest paths
    • Minimal flow / graph connectivity
    • Minimal number of edges to remove in order to break cycles
  • Techniques:
    • Implement standard algorithms the Prolog way
    • OOP in Prolog (for making the graph library easily reusable and extensible)
    • Efficient Prolog programming! – Exploit indexing, caching, …
    • Exploit library(clpfd) – “Constraint Logic Programming for Finite Domains” library of SWI-Prolog

Seminar talk on this topic

Type Flow

  • Problem: The type flow problem and solution approaches will be introduced during the seminar phase by participants from the MoSA course.
  • Starting point: Code of dsp
  • Aim: Make type flow analyzes fast enough to run permanently in the background
  • Techniques:
    • Efficient Prolog programming! – Exploit indexing, caching, …
    • Incrementality! – Recompute only parts affected by the latest changes (edits)

Data and Control Flow

  • Problem: We shall focus on the most important data in object-oriented languages, object references (ignoring primitive data types) and address the implementation, evaluation and improvement of interprocedural algorithms for determining
    • control flow information,
    • points-to information and
    • reference flow information.
  • Starting point: Code of A. G. (intraprocedural control flow) and S.M. (intraprocedural points-to analysis).
  • Aim: Make context-sensitive interprocedural points-to analysis efficient enough for practical use on medium to large scale Java programs.
  • Challenges: Efficient static approximation of dynamic binding targets by precise points-to analysis (PTA), properly balancing the added costs of more precise analyzes with the gained efficiency (better precision means we know that we do not need to analyze methods that will not be called). Precision levels:
    • Intraprocedural: Field-sensitivity, Object-sensitivity, Array-sensitivity, Flow-sensitivity
    • Interprocedural: Context-sensitivity for various combinations of the above intraprocedural precision levels
  • Techniques:
    • Implement existing algorithms for (cloning-based) interprocedural points-to analysis (extend the existing code base)
    • Evaluate these algorithms
    • Use our joint brain power to combine and improve them, e.g. towards
      • summary-based interprocedural points-to analysis!?!
      • demand-driven analysis
      • incremental analysis

Integration scenario

As an application that integrates all of the above we aim to implement the specialization analysis of tip & al.

Last modified: 2017/08/29 23:13
*