ACS/Part III Project suggestions

Students interested in any of the following should contact me by email.

Fingerprinting static analysis findings

There are lots of tools for statically detecting programming errors. However, in practice it is impossible to resolve all findings on a codebase: some will be false positives, others will be low priority to fix. What would be useful in this context would be a way of tracking findings over time.

For this project you will look at developing fingerprinting techniques for static analysis findings. These techniques should be as stable as possible over code changes i.e. if new lines are added, or some refactoring applied the system should be able to tell that this is the same finding as before.

Various techniques exist for code fingerprinting which could be investigated here but my hypothesis is that the best results will come from choosing different techniques for different checks. If this turns out to be the case then approaches for choosing the right technique for a check will also be interesting.

Proposed work: The Google Error Prone Java compiler provides a large range of checks and is easy to apply to Java code. We would then evaluate fingerprinting approaches against real evolving code bases e.g. taken from Github.

Automatic build file generation

There are a wide variety of build systems available. For example Java developers might use a Makefile, Ant, Maven or Gradle. This project involves using system call interposition to record the dependencies and steps of a build process as it runs. This information might be used to translate to a different build system or to monitor incremental builds to detect when a build is invalid.

Starting point: Milos Gligoric et al., "Automated migration of build scripts using dynamic analysis and search-based refactoring", Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications.

Language agnostic analysis of programming patterns

Kythe is a project originating from Google that tries to unite software support for programming across many programming languages and environments.

``The Kythe project was founded to provide and support tools and standards that encourage interoperability among programs that manipulate source code. At a high level, the main goal of Kythe is to provide a standard, language-agnostic interchange mechanism, allowing tools that operate on source code --- including build systems, compilers, interpreters, static analyses, editors, code-review applications, and more --- to share information with each other smoothly.'' [1]

Each language that Kythe supports has a plug-in module that translates code from that language into Kythe-compliant graph artifacts.

Your task, should you choose to accept it, will be in several parts:

  1. Use the existing Java and C++ plug-ins for Kythe to do 'language-agnostic' analysis of programming habits, styles, idioms and patterns. For example, a code search engine that finds certain strings by name and type of code object (function, variable, literal, etc). Or, a type-based search engine that allows you to find all functions that match a certain signature. More importantly, detection of either (a) deprecated, (b) dangerous, or (c) naive programming practices. One thing to keep an eye on might be the way programmers manage objects allocated in the heap. Are there any signature differences that you can detect between GC-managed objects and manually-managed memory? How does that show up in the Kythe graph structure?
  2. Extend Kythe to other languages. We suggest Fortran-90 as a starting point. You should consult the documentation "Adding Support for a New Language" [2] and the Kythe Schema [3]. This will probably also require understanding of Google's protocol-buffers [4] and Kythe's index pack format [5]. If you choose to work in Haskell (recommended), you may find Fortran support implemented in CamFort [6] or Language.Fortran [7] useful, as well as Haskell support for protocol-buffers [8].
  3. Use your Kythe plug-in for Fortran, as far as it goes, to perform various analyses of existing scientific code bases written in Fortran.
  4. Integrate with the CamFort Fortran refactoring tool to automatically fix, as far as possible, any of the programming practices identified by your analysis.

Differential testing of Fortran refactoring

We are running a research project to apply programming language research to support programming in science, via tools and languages (a synposis can be found here: http://www.cl.cam.ac.uk/research/dtg/naps. We have developed CamFort, a research infrastructure for analysing and transforming Fortran code base, as well as extending the core language. Fortran remains a popular language for scientific computing, partly due to the legacy of long-lived models written in Fortran that continue to be useful. However, older versions of the Fortran language have various features which are not helpful (often hard to understand or tending to lead to sources of errors). One approach is to ‘upgrade’ existing code base by applying refactoring tools to transform older Fortran into a modern style [4]. However, doing so whilst preserving the semantics of the existing program is difficult and users often distrust large scale refactorings. This project will develop an automatic test generation system refactorings, similar in style to QuickCheck for Fortran, aimed at refactorings.

QuickCheck provides a property-based testing framework which automatically generates a range of representative input data samples for a piece of code [1]. This reduces programmer effort, provides wider coverage, and provides counterexamples when a property is violated. In the case of a refactoring r applied to some program p, the test property is thus p = r(p). This is a kind of differential test, between two programs which are intended to be the same [3].

In the case of scientific modelling in Fortran, our experience is that most code bases exhibit poor levels of modularity (partly a consequence of the language design and programming style). Instead, subroutines and functions tend to be large, spanning hundreds to thousands of lines with complex internal control flow. It is unlikely that applying the QuickCheck approach as-is to such coarse-grained code will expose the source of any discrepancies that may be introduced during refactoring. Furthermore, more coarse-grained modules tend to have a large number of input dependencies, requiring very large test runs.

Instead, this project will develop techniques for increasing the granularity of the code base, hidden from the user, to provide more fine grained, targeted information on individual refactoring transformations. This project will use the CamFort infrastructure as a basis. CamFort parses a large subset of Fortran code and provides a functional DSL embedded in Haskell for defining analyses and refactoring transformations over Haskell.

Depending on the locality of the refactoring there are probably two main approaches to consider:

(Implicit) modularisation for local changes

If changes are made to a small part of an AST then this piece of code could be functionalised (turned into a function). This requires an analysis of the data flow, to find out what is live-in and live-out and thus what needs to be passed in as a parameter and out with the return result (also beware side effects). This also requires an analysis of the control flow to make sure there are no jumps into the middle of this code block or out (Fortran still has GOTO, even though it is deprecated).

For example, consider the following refactoring of two nested ‘do’-loops into the ‘forall’ notation (which is somewhere inside a larger program)

  do i = 1, n 
     do j = 1, m
       a(i, j) = i * j    
     end do
  end do

 A 
----->  
forall (i = 1:n, j = 1:m)
     a(i, j) = i * j
  end forall



B

[Note this refactoring is not currently implemented in CamFort, this would be a nice case study that should be added into CamFort as part of the project. The refactoring is fairly straightfoward, but needs to do a simple effect and dependency analysis].

A differential test can be generated where the pre- and post-refactored fragment is modularised as a function e.g.,

function loop(a, n, m) 
  integer n, m
  real a(n, m)
  real, dimension(n, m) :: loop
  do i = 1, n 
    do j = 1, m
      a(i, j) = i * j
    end do
  end do
  loop = a
end function

 A’
----->  
function loop(a, n, m) 
  integer n, m
  real a(n, m)
  real, dimension(n, m) :: loop
  forall (i = 1:n, j = 1:m)
    a(i, j) = i * j
  end forall
  loop = a
end function   



B’

These functions can then be tested independently for equivalence by auto-generating tests based on the input types (in the style of QuickCheck).

Program slicing (for global changes)

In the case of non-local transformation, e.g., refactoring a shared data structure or refactoring equivalence statements and common blocks (functionality provided by CamFort), then program slicing [2] might be a more appropriate technique to select all parts of a program related to particular changes by control- and data-flow.

For example, the following refactoring eliminates the use of an ‘equivalence statement’ (which aliases a single piece of memory to two variables, often a source of bugs).

integer :: x, y, i, a
equivalence (x, y)
x = 0
a = 1
x = 5
do i = 1, x
  x = x + i
  a = a * i
end do
print '(i8, i8, i8)', x, y, a
----->  
integer :: x, y, i, a

x = 0
a = 1
x = 5
do i = 1, x
  x = x + i
  a = a * i
  y = x
end do
print '(i8, i8, i8)', x, y, a

The refactoring eliminates the equivalence statement by inserting ‘copy’ statements whenever ‘x’ or ‘y’ is updated.

Not all parts of the program are related to ‘x’ and ‘y’ though, such as the variable ‘a’ and ‘i’, although the control flow related to ‘i’ is important for dataflow of ‘x’. A program slice on the ‘x’ and ‘y’ for the pre- and post-refactored code would yield:

integer :: x, y, i, a
equivalence (x, y)
x = 0
a = 1
x = 5
do i = 1, x
  x = x + i
  a = a * i
end do
print '(i8, i8, i8)', x, y, a
----->  
integer :: x, y, i, a

x = 0
a = 1
x = 5
do i = 1, x
  x = x + i
  a = a * i
  y = x
end do
print '(i8, i8, i8)', x, y, a

(we might completely erase the ‘print’ statement as well since testing may perform equality tests on the outputs rather than checking output traces, this is an open question).

The sliced programs can then have inputs generated, in a QuickCheck style, which address only the relevant inputs and outputs of the program. Program slicing might be considered on parts of a whole code base at a time. For example, common-block elimination can affect an entire code base, but testing a sliced version of the whole code base is likely difficult (time consuming to generate and run enough tests). Some kind of decomposition is likely useful and informative still.

Open research questions are to what extent these two approaches (modularisation or slicing) can be combined and selected for on a case-by-case basis, and which will be more effective.

Evaluation

  • Applicability - The tool should work with the common-block and equivalence elimination features of CamFort, and the forall introduction refactoring (which should be introduced as part of the the project).
  • Coverage - The tool should be able to generate tests that are shown to provide a significant degree of coverage of branches in a program. A coverage analysis may be included to improve upon this further by looking at the source code (although this isn’t part of the usual QuickCheck approach, which does not do a coverage analysis).
  • Flexible - The tool should support generation of test data for all built-in datatypes and be able to deal with arbitrary dimension matrices.

References

[1] Koen Claessen and John Hughes, Quickcheck: a lightweight tool for random testing of Haskell programs, ACM SIGPLAN Notices 46 (2011), no. 4, 53–64.
[2] Keith Brian Gallagher and James R. Lyle, Using program slicing in software maintenance, Software Engineering, IEEE Transactions on 17 (1991), no. 8, 751–761.
[3] William M McKeeman, Differential testing for software, Digital Technical Journal 10 (1998), no. 1, 100–107.
[4] Dominic Orchard, Andrew Rice, Upgrading Fortran source code using automatic refactoring, WRT'13 (ACM Workshop on Refactoring Tools 2013, colocated with SPLASH 2013) http://www.cl.cam.ac.uk/~dao29/publ/wrt13-orchard-rice.pdf