Tag Archives: Static Analysis

Design your Analysis!

Does software engineering matter for your research prototype? Johannes and I published a paper in the latest SOAP Workshop at PLDI and tend to answer “yes of course!”.  We inspected a data flow analysis using the IFDS framework. Even though we only discuss and inspect this particular case in the paper, the argument itself is, however, more general.

When developing static code analysis, we – as in we the researchers or practitioners – forget everything that we learned in our software engineering classes and write code that is very much sequential and not modularized very well. Given that the domain can be pretty challenging and may require intensive testing it is very surprising to me that we tend to write code that is hard to test in isolation. So what we do most of the time is integration testing with huge chunks of test code that we analyze and then check the results against our expectations for the chunks. But this also means that if your analysis target is large so is your expectation set and tracing and fixing bugs in your implementation can be a pretty tough task.

We faced this problem while implementing FlowTwist using Heros which is an implementation of the IFDS framework/solver by Reps et al. The framework forces you to separate your analysis steps into so called flow functions that represent treatments of data flow facts at instructions. It thus forces you to design along the lines of the framework which is a good first step.

However, a simple flow function implementation has to cover a lot of concerns such as the treatment of assignments, conditionals, field accesses, etc. Therefore, our flow function implementations tended to become incredibly long pieces of code (over 300 LOC) that were hard to read, incredibly hard to explain to other people, hard to test, hard to maintain and impossible to reuse. So plainly a big big mess with a method header.

Given that we actually teach students not to write code in this manner, we were – let’s say – unsatisfied with the situation and refactored. We quickly observed that we were handling multiple concerns in the same flow function. What took a while is the insight that we actually scattered things over the four flow function types.

Phases and Propagators in FlowTwist’s design. F is a Fact and U is actually the union operator

So we came up with a new design of Propagators that factored out these concerns in a single neat and tidy class. We quickly became aware that we needed a way of expressing a sequence like first filter then do expensive calculations in order to produce something that will actually work and introduced phases as a means to organize propagators. The paper goes into the details here.

In the end, the story is that software engineering matters even in your research prototypes and – YES – you should care about it. Believe it or not sometimes your research actually gets picked up and continued or extended by other people. The likelihood of this happening will dramatically increase if your prototype is easily understandable, testable, maintainable and extendable. Even though I haven’t got any proof for this last very bold sentence, I believe it to be true – and might be supported by the gods of software engineering.

PEAKS – Project looking for heroes

peaks_logo_mediumYou are in the final steps of your master thesis? I am currently looking for a young researcher (M.Sc. or comparable preferably computer science or mathematics, preferably heroes of all kind) that is interested in a one-year research project in static analysis and security. It is actually a nice way to look into daily scientific work before deciding to do your PhD (or not) or to get a smooth start into your own PhD project if you have already decided.

The project that needs a hero is PEAKS. The name is an acronym for Platform for the Efficient Analysis and Secure Composition of Software Components (and just works as an acronym in German). It tries to solve (or alleviate) the dilemma you are facing when trying to write secure software efficiently using pre-existing software components. Currently, it is pretty hard to limit the libraries you use to the privileges you want to give to them. In a common setting these libraries run with the same privileges as their hosting process and can therefore do all the good and all the harm as the process can.

We would like to change that, because we believe this could be solved better!

Following the Principle of Least Authority,  software libraries should only be equipped with the privileges necessary for their job. There are two possible ways to achieve this… You could either isolate the components from the rest of the application and only process those requests that are privileged or you could monitor its behavior and make decisions based on the monitoring.

In PEAKS we follow the latter approach to reach an effective isolation through the monitoring of static properties. We analyze Java libraries and try to find transgressions of the Object-Capability Model. In the OCaps Model objects in an object-oriented system are both the subject and the privilege of the security system. Or better: they could be used in either way. Here the privileges – called capabilities – only can be transferred from one subject to the other in four ways:

  1. The initial setup of the system is granting it
  2. Parenthood – a new object is created. The creator owns the capability to call the object.
  3. Endowment – during the creation of and object the creator endows the newly created object with a subset of its own capabilities.
  4. Introduction – when an object calls another, it can choose to transfer the capabilities to the other object.

It is obvious that some widely used object-oriented programming models such as Java can violate this principle. Though static analysis we try to find these transgressions in libraries. They can be of the following types.

static callsStatic Calls

Through static calls you can construct a so called ambient resource. Capabilities can be shared between subjects that otherwise wouldn’t have access to it. You lose the ability to control the explicit dispensation of capabilities.

However, not every static call is harmful here. In certain circumstances functionally pure methods might be allowed.

intrusive reflectionIntrusive Reflection

The most prominent and excessively used security feature of an object-oriented system is information hiding. If you break information hiding the inner state of an object can be read or altered. Subjects possessing a  capability can use intrusive reflection to break information hiding and effectively gain all transitively accessible capabilities.

native callsNative Calls

When using Java you might not be aware that most of the calls you make sooner or later end up executing code that is directly compiled from C/C++ to native code residing either in the Java Class Library or the software library you are currently using. This code is executed outside the security context of the Java Virtual Machine and can access and alter the VM memory directly. Thus, one of the major requirements of the OCaps model – the unforgeability of references – can not be guaranteed any more.

You might have seen in the past week, that I am offering a few student thesis projects in this area:

The work done in these thesis projects complements PEAKS as it forms a baseline for further library analysis because software libraries usually call JCL methods as well.

Are you interested in being that hero?

The project team already did a lot of preparatory work and we already have a running prototype. Your task will be to develop this prototype into a running proof-of-concept together with the project team, to evaluate it and strengthen the theory behind the approach. Of course publications are part of the job as well.

You should be:

  • a graduate of computer science or mathematics (M.Sc. or comparable)
  • a good software engineer – programming is definitely required here
  • able to talk in terms of security – privilege and protection domain are notions that you understand
  • a team player
  • bright
  • brilliant
  • a fluent speaker of English and (a plus!) German

You are a heroine? I especially encourage female computer scientists or mathematicians to apply for the job!

Please contact me over one of these channels if you are interested in the job.


PEAKS is funded as part of the Software Campus initiative of the German Ministry for Research and Education (BMBF) filed under 01|S12054.