Research @Lund University

Efficient Demand Evaluation of Fixed-Point Attributes: A Dive into On-Demand Static Analysis

Software analysis tools are everywhere—from your favorite IDE to the powerful linters running in the background of production environments. One of the driving forces behind these tools is static analysis, the technique of examining code without executing it. If you’ve ever wondered how your IDE catches bugs before you even run the program, static analysis has probably been hard at work in the background.

In our latest research (Efficient Demand Evaluation of Fixed-Point Attributes Using Static Analysis), my co-authors and I tackled an interesting problem in the world of static program analysis: how to make certain kinds of attribute grammars more efficient.

Static Analysis and Attribute Grammars—A Quick Primer

When we talk about static analysis, we often deal with solving dependencies between different parts of the code. These dependencies are sometimes cyclic, meaning some program properties depend on each other. Traditional static analysis tools need to compute a “fixed-point” for these cyclic dependencies, which is where our research comes in.

Enter Reference Attribute Grammars (RAGs)—a powerful formalism used to specify such dependencies. While historically aimed at compilers, RAGs are now applied to a variety of program analysis problems, including detecting things like dead code and null-pointer dereferences.

But like all good things, RAGs have a catch: existing evaluation methods for cyclic dependencies (called circular attributes) aren’t always efficient. Some of the best-known algorithms don’t scale well for complex languages like Java. What did we do about it? Well, we proposed a new algorithm, of course.

So What’s the Problem?

Imagine you’re analyzing a large codebase (think of something like a huge Java project). The goal is to determine the null-pointer dereferences in the program. Using older algorithms for circular attributes, you’d have to recompute a lot of unnecessary dependencies repeatedly, which is both slow and inefficient.

The core issue? Not all attributes are cyclic, but older algorithms treated them as if they were. That’s like treating everyone as a suspect in a mystery where most people were just bystanders.

Our Solution: An Optimized Demand Evaluation Algorithm

Our algorithm improves upon older methods by statically identifying attributes that can never be part of a cycle and treating them more efficiently. This leads to significant performance boosts (we’re talking up to 22x faster in some cases!).

We implemented this in JastAdd, a metaprogramming system for RAGs. In doing so, we optimized evaluations across a range of real-world case studies, including null-pointer dereference analysis and dead-assignment analysis.

One of the cool aspects of our approach is that it not only optimizes existing tools but also lays the groundwork for future analyses—imagine compiler tools running more efficiently or catching more bugs before you even hit compile.

Why Should You Care?

If you’re a developer or someone working in the field of software tools, this work could directly impact how fast and efficiently your tools operate. Faster tools mean more productivity, less waiting, and fewer headaches.

If you’re more academically inclined, this is a nice example of how formal methods and static analysis meet real-world needs, improving both academic understanding and practical implementations. Plus, it’s always fun to solve a mystery (even if it’s a computational one)!

To wrap up, this work highlights the importance of smarter demand-driven evaluation in static analysis, something that’s becoming increasingly essential as our software grows larger and more complex.

You can find the link to the full paper here.

JFeature: Exploring Java 8 Features with Static Analysis

Our initial goal was to evaluate the precision of IntraJ on Java projects from the well-known DaCapo Benchmark Suite. These projects seemed like a good starting point, but after diving in, I quickly realized a key problem: none of the DaCapo projects are written in Java 8.

Determined to find suitable test cases, I expanded my search to other popular corpora (yes, it’s “corpora,” not “corpuses”). To my surprise, the majority of corpora commonly used in static analysis don’t include Java 8 projects either. This was a significant gap, especially considering the importance of Java 8 features like:

  • Lambda Expressions
  • Intersection Casts
  • Default Methods
  • Method and Constructor References

Finding projects that heavily rely on these features was becoming a challenge. I turned to the literature, expecting to find resources or tools that could help. But again, I found nothing—no papers, no tools designed to extract this information at the source level.

That’s when I had a realization: this gap in the research presented a great opportunity to do something new. I decided to pause the IntraJ project and began working on a new tool: JFeature.

JFeature aims to fill this gap by identifying and analyzing projects that extensively use Java 8 features. It’s an exciting direction, and I’m eager to see where it leads!

IntraJ: A Precise Framework for Source-Level Control-Flow Analysis

IntraJ is an application of the language independent framework IntraCFG for the Java language, build as an extension of the ExtendJ Java Compiler. More details can be found in the following paper:

With IntraJ you can:

  • construct intra-procedural Control Flow Graph,
  • (DAA) detect Dead assignments in your codebase, and
  • (NPA) detect occurences of NullPointerException. You can run IntraJ on other Java codebases (in Java-4, Java-5, Java-6, and Java-7) in order to construct CFGs and get DAA and NPA analysis results.

Will it Blend? Composable Source Code Analysis

In collaboration with: @Khashayar Etemadi, @Deepika Tiwari, @Mohammad Reza, @Momina Rizwan and @Matthías Páll Gissurarson

In the beginning, there were command line tools. Each was beautifully designed and served a single function, such as wc and cat. A single editor was born, ed, to serve as the standard editor. However, mankind was convinced of its greatness, and wanted more. They started small and wrote vi, a visual interface for ed. An editor with a simple interface and humble features, which greatly improved productivity. However, in its success, mankind grew vain and wrote ever more complex editors, with grand interfaces and rich graphics, with feature upon feature built into the editor itself. But they could not agree. Some wanted to use a LISP dialect, others shouted for JavaScript. And thus, like the fall of the tower of Babel, the editor wars began, with each editor writing features integrated into its very being, completely assimilated into its very core. Mankind grew to like some of these features, but a problem emerged: how can we share these features between editors so that we may all benefit, and avoid another bloodshed like the editor wars? In this paper, we describe an interface and units for that interface which abstract common GUI editor operations into simple, one-feature-per-unit command line programs, and peace in our time.