soft-an02/report.tex

\documentclass[11pt,a4paper]{scrartcl}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage[utf8]{inputenc}
\usepackage[margin=2.25cm]{geometry}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{lmodern}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{float}
\usepackage{tikz}
\usepackage{listings}
\usepackage{pgfplots}
\pgfplotsset{compat=1.18}
\usepackage{subcaption}
\setlength{\parindent}{0cm}
\setlength{\parskip}{0.3em}
\hypersetup{pdfborder={0 0 0}}
%\usepackage[nomessages]{fp} no easter eggs this time
\usepackage{amsmath}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\usepackage{minted}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

\lstdefinestyle{mystyle}{
  backgroundcolor=\color{backcolour},   
  commentstyle=\color{codegreen},
  keywordstyle=\color{magenta},
  keywordstyle=[2]{\color{olive}},
  numberstyle=\tiny\color{codegray},
  stringstyle=\color{codepurple},
  basicstyle=\ttfamily\footnotesize,
  breakatwhitespace=false,         
  breaklines=true,                 
  captionpos=b,  
  keepspaces=true,                 
  numbers=left,  
  numbersep=5pt,
  showspaces=false,                
  showstringspaces=false,
  showtabs=false,
  tabsize=2,
  aboveskip=0.8em,
  belowcaptionskip=0.8em
}
\lstset{style=mystyle}

\geometry{left=2cm,right=2cm,top=2cm,bottom=3cm}
\title{
\vspace{-5ex} 
Assignment 2 -- Software Analysis \\\vspace{0.5cm}
\Large Static Analysis with Infer
\vspace{-1ex} 
}
\author{Claudio Maggioni}
\date{\vspace{-3ex}}

\begin{document}
\maketitle

\section{Project selection}
Given that this assignment draws parallels with the class of Software Design and
Modelling of last semester, specifically regarding static analyzers, I choose to
analyze the same project I analyzed in the past with PMD and SonarQube using
Infer\footnote{\url{https://fbinfer.com/}} to make
for an interesting comparison between static analysis paradigms.

The project I analyze is therefore
\href{https://github.com/apache/commons-lang}{\textbf{apache/commons-lang}}.

\subsection{The Apache Commons Lang Project}
The Apache Commons family of libraries is an Apache Software
Foundation\footnote{\url{https://apache.org/}} sponsored collection of Java
libraries designed to complement the standard libraries of Java. The Apache
Commons Lang project focuses on classes that would have fitted in the
\textit{java.lang} package if they were included with Java.

All the source and test classes are contained within in the package
\textit{org.apache.commons.lang3} or in a sub-package of that package. For the
sake of brevity, this prefix is omitted from now on when mentioning file paths
and classes in the project.

I choose to analyze version 3.12.0 of the library (i.e.\ the code under the
\textit{git} tag \textit{rel/commons-lang-3.12.0}) because it is the same
version analyzed during the SDM class.

To verify that the project satisfies the 5000 lines of code requirement, I run
the \textit{cloc} tool. Results are shown in table \ref{tab:cloc}. Given the
project has more than 86,000 lines of Java code, this requirement is satisfied.

\begin{table}[H]
  \centering
  \begin{tabular}{lrrrr}
    \toprule
    Language & Files & Blank & Comment & Code \\
    \midrule
    Java & 409 & 15,790 & 60,363 & 86,056 \\ 
    HTML & 22 & 1,015 & 100 & 13,028 \\ 
    Text & 30 & 1,858 & 0 & 12,415 \\ 
    XML & 38 & 434 & 539 & 4,819 \\ 
    Maven & 1 & 31 & 37 & 940 \\ 
    JavaScript & 5 & 21 & 78 & 698 \\ 
    Markdown & 3 & 38 & 0 & 202 \\ 
    CSS & 4 & 36 & 66 & 140 \\ 
    Velocity Template Language & 1 & 23 & 31 & 90 \\ 
    Groovy & 1 & 12 & 22 & 81 \\ 
    YAML & 3 & 12 & 42 & 55 \\ 
    Bourne Shell & 1 & 0 & 2 & 2 \\
    \midrule
    Total & 518 & 19,270 & 61,280 & 118,526 \\
    \bottomrule
  \end{tabular}
  \caption{Output of the \textit{cloc} tool for the Apache Commons Lang project
    at tag \textit{rel/commons-lang-3.12.0} (before fixes are applied).}
  \label{tab:cloc}
\end{table}

\section{Running the Infer tool}

The relevant source code to analyze has been copied to the directory
\textit{before} in the assignment repository

\begin{center}
\href{https://gitlab.com/usi-si-teaching/msde/2022-2023/software-analysis/maggioni/assignment-2}{\textit{usi-si-teaching/msde/2022-2023/software-analysis/maggioni/assignment-2}}
\end{center}

on \textit{gitlab.com}. The script \textit{docker-infer.sh} can be executed to
automatically run the Infer tool using default options through the course
tools docker image \textit{bugcounting/satools:y23}.

The script executes Infer in Maven capture mode executing the \textit{compile}
and \textit{test} targets while disabling the Apache RAT software license
checker (which fails for this release) and the Animal Sniffer Maven plugin do to
the failure message ``This feature requires ASM7'' it produces if ran.  Since
unit tests are executed, running the script before and after the warning guided
refactoring ensures the fixes I introduce do not introduce regressions.

The analysis outputs
are located in \textit{before/infer-out/report.txt}.

\section{Results}

Table \ref{tab:infer} shows the results of the analysis performed by Infer
providing comments on true and false positives and the actions taken for each
result.

\begin{table}[H]
   \small
    \begin{tabular}{@{}llp{1.2cm}p{0.65cm}p{6cm}@{}}
\toprule
\textbf{File} & \textbf{Line} & \textbf{Kind} & \textbf{True Pos.} &
\textbf{Reason why flagged expression is a false positive} \\ \midrule
AnnotationUtils.java & 72 & Null & Yes & \\
reflect/MethodUtils.java & 486 & Null & Yes & \\
concurrent/MultiBackgroundInitializer.java & 160 & Thread Safety & Yes & \\
\midrule
builder/ToStringBuilder.java & 223 & Null & No & \multirow{2}{6cm}{Infer flags
        the value \texttt{null} when used as a nullable method argument} \\
builder/ReflectionToStringBuilder.java & 131 & Null & No & \\
\midrule
time/DurationUtils.java & 142 & Null & No & The method which
        may return a null value returns a non-null value if its parameter is
        non-null, and a non-null parameter is given \\ 
\midrule 
CharSetUtils.java & 181 & Null & No & According to \textit{java.lang}
documentation, the method always returns a non-null value \\
\midrule
reflect/FieldUtils.java & 126 & Null & No & 
\multirow{5}{6cm}{A utility method is used to guard the dereference reported
with an exception throw} \\
reflect/FieldUtils.java & 341 & Null & No & \\
reflect/FieldUtils.java & 385 & Null & No & \\
reflect/FieldUtils.java & 599 & Null & No & \\
reflect/FieldUtils.java & 644 & Null & No & \\
\midrule
reflect/MethodUtils.java & 987 & Null & No & The method which may return a null
value returns a non-null value if its parameter is non-null, and a
non-null parameter is always given according to the \textit{java.lang}
documentation for the inner nested method \\ \bottomrule
\end{tabular}
    \caption{Results of the Infer static analysis tool execution with default
    options. \textit{True Pos.} denotes whether a result is a true positive,
    while \textit{Kind} denotes with \textit{Null} and \textit{Thread Safety}
    respectively null dereference warnings and thread safety violations.}
    \label{tab:infer}
\end{table}

In total Infer reports 13 warnings, 12 of which are null dereference warnings
and 1 is a thread safety violation. Of all warnings, 3 are true positives and 10
are false positives, resulting in a precision of 23\%.
These values are summarized in table \ref{tab:num}.

\begin{table}[H]
    \centering
\begin{tabular}{@{}ll@{}}
\toprule
Total number of warnings:  & 13 \\ \midrule
Null dereference warnings: & 12 \\
Thread safety violations:  & 1  \\ \midrule
True positives:            & 3  \\
False positives:           & 10 \\ \bottomrule
\end{tabular}
    \caption{Quantitative results of the static analysis performed by Infer.}
    \label{tab:num}
\end{table}

\subsection{False Positives}

As can be deduced from table \ref{tab:infer}, Infer especially struggles at
determining Vthe null safety of nested method calls or non-trivial data flow
paths. This is sometimes caused by insufficient knowledge of the nullability
contracts of the Java standard library (e.g. \textit{java.lang} package).

In other cases, the flagged expression is guarded by an utility method throwing
an exception if its value is indeed \texttt{null}. One of such guards is the
\mintinline{java}{static Validate.notNull(Object, String, Object...)} method,
which checks if its first argument is null and throws a
\texttt{NullPointerException} with a ``pretty'' message composed from a format
string and variadic arguments if so.

Additionally, Infer seems to struggle with boxed primitives and not
understanding that their value is always non-null by construction. As an example
I provide the warning reported in the file \textit{time/DurationUtils.java}:

\begin{listing}[H]
\begin{minted}[linenos,firstnumber=139]{java}
public static int toMillisInt(final Duration duration) {
    Objects.requireNonNull(duration, "duration");
    // intValue() does not do a narrowing conversion here
    return LONG_TO_INT_RANGE.fit(Long.valueOf(duration.toMillis())).intValue();
}
\end{minted}
    \caption{Method \textit{toMillisInt(Duration)} of class
    \textit{time.DurationUtils} in Apache Commons Lang 3.12.0.}
\end{listing}

Here Infer reports that the first argument of
\mintinline{java}{LONG_TO_INT_RANGE.fit(Long)} may be null. However, the return
value of \mintinline{java}{Long.valueOf(long)} is always non-null since the
method simply boxes its \mintinline{java}{long} argument.

Finally, some warnings are caused by Infer flagging the use of the \texttt{null}
keyword as a method argument for methods that would accept a nullable argument
in that position without causing null dereferences. This warning could point to 
a potential ambiguity is selecting the right method to call at
compile time given the argument types (i.e. static dispatching), as
\texttt{null} is a valid expression of all object types. For example, in the
given class:

\begin{minted}{java}
class C {
  m(String s) {}
  m(Object o) {}
}
\end{minted} 

A call to \mintinline{java}{C.m(null)} would be ambiguous as \texttt{null} is
both a \texttt{String} and an \texttt{Object}, thus a cast to either type woule
be required to make the code compile. However, the warnings reported by Infer do
not present such ambiguity as in those cases overloaded methods have different
numbers of parameters. Additionally, even introducing explicit casts for all
\texttt{null} arguments does not extinguish the warning. Therefore, I can not
find a conclusive explaination on the nature of the false positive, however I
can attest to these instances being indeed false positives by having manually
verified that the methods in question indeed can accept a null value without
causing null dereferences.

\subsection{True Positives}

In this section I now cover the warnings that are true positives and thus are
causes for refactoring.

A copy of the entire code base where refactoring has been applied can be found
in the \textit{after} directory of the assignment's repository.

\begin{listing}[H]
\begin{minted}[linenos,firstnumber=71]{java}
@Override
protected String getShortClassName(final Class<?> cls) {
    for (final Class<?> iface : ClassUtils.getAllInterfaces(cls)) {
        if (Annotation.class.isAssignableFrom(iface)) {
            return "@" + iface.getName();
        }
    }
    return StringUtils.EMPTY;
}
\end{minted}
    \caption{Method \textit{getShortClassName(Class$<$?$>$)} of class
    \textit{AnnotationUtils} in Apache Commons Lang 3.12.0.}
    \label{lst:ann}
\end{listing}

Listing \ref{lst:ann} shows the location of the first true positive warning.
Here, \mintinline{java}{ClassUtils.getAllInterfaces(cls)} at line 73 may
return a null value thus potentially causing a null dereference when iterating
in the enhanced for loop. Indeed, the method's implementation shows that while
for non-null \texttt{cls} values the return value is non-null, if \texttt{cls}
is null \texttt{null} is returned. Since the method is protected its signature
is visible to all child classes, even ones potentially outside of the Apache
Commons Lang library. As the method's documentation does not specify anything
about the nullability of the argument \texttt{cls}, its value may indeed be null
and thus a refactor is needed to avoid the potential null dereference.

I choose to simply return \mintinline{java}{StringUtils.EMPTY} when \texttt{cls}
is null. The refactored implementation can be found in listing \ref{lst:ann2}.

\begin{listing}[H]
\begin{minted}[linenos,firstnumber=71]{java}
@Override
protected String getShortClassName(final Class<?> cls) {
    final List<Class<?>> interfaces = ClassUtils.getAllInterfaces(cls);
    if (interfaces == null) {
        return StringUtils.EMPTY;
    }

    for (final Class<?> iface : interfaces) {
        if (Annotation.class.isAssignableFrom(iface)) {
            return "@" + iface.getName();
        }
    }
    return StringUtils.EMPTY;
}
\end{minted}
    \caption{Refactor of method \textit{getShortClassName(Class$<$?$>$)} of
    class \textit{AnnotationUtils}.}
    \label{lst:ann2}
\end{listing}

Next, class \textit{reflect.MethodUtils} contains a bug due to insufficient
defensiveness when accepting the method parameters.

\begin{listing}[H]
    \small
\begin{minted}[linenos,firstnumber=461,breaklines]{java}
static Object[] getVarArgs(final Object[] args, final Class<?>[] methodParameterTypes) {
    if (args.length == methodParameterTypes.length && (args[args.length - 1] == null ||
            args[args.length - 1].getClass().equals(methodParameterTypes[methodParameterTypes.length - 1]))) {
        // The args array is already in the canonical form for the method.
        return args;
    }

    // Construct a new array matching the method's declared parameter types.
    final Object[] newArgs = new Object[methodParameterTypes.length];

    // Copy the normal (non-varargs) parameters
    System.arraycopy(args, 0, newArgs, 0, methodParameterTypes.length - 1);

    // Construct a new array for the variadic parameters
    final Class<?> varArgComponentType = methodParameterTypes[methodParameterTypes.length - 1].getComponentType();
    final int varArgLength = args.length - methodParameterTypes.length + 1;

    Object varArgsArray = Array.newInstance(ClassUtils.primitiveToWrapper(varArgComponentType), varArgLength);
    // Copy the variadic arguments into the varargs array.
    System.arraycopy(args, methodParameterTypes.length - 1, varArgsArray, 0, varArgLength);

    if (varArgComponentType.isPrimitive()) {
        // unbox from wrapper type to primitive type
        varArgsArray = ArrayUtils.toPrimitive(varArgsArray);
    }

    // Store the varargs array in the last position of the array to return
    newArgs[methodParameterTypes.length - 1] = varArgsArray;

    // Return the canonical varargs array.
    return newArgs;
}
\end{minted}
    \caption{Method \textit{getVarArgs(Object[], Class$<$?$>$[])} of class
    \textit{reflect.MethodUtils} in Apache Commons Lang 3.12.0.}
    \label{lst:met}
\end{listing}

Line 482 of the class (listed in listing \ref{lst:met}) is correctly flagged as
a potential null dereference as \texttt{varArgComponentType} may be null.
Indeed, according to the documentation of the method generating its value, the
variable is null when the last value in the array \texttt{methodParameterTypes}
is a class object for a non-array class.  Such value would violate the method's
contract, which specifies that the array should correspond to class types for
the arguments of a variadic method, and the last argument in a variadic method
is always an array. However, this is not checked defensively, and we can fix
this by introducing a check after line 475 like this:

\begin{minted}{java}
if (varArgComponentType == null) {
    throw new IllegalArgumentException("last method parameter type is not an array");
}
\end{minted}

It is quite interesting Infer was able to detect this null dereference as it
stems from a lack of sufficient defensiveness. Improper use of the method would
trigger a \textit{NullPointerException} without any useful message indicating
the precondition violation.

Finally, the last warning involves class
\textit{concurrent.MultiBackgroundInitializer}. The relevant method source code
is shown in listing \ref{lst:mbi}.

\begin{listing}[H]
\begin{minted}[linenos,firstnumber=157]{java}
@Override
protected int getTaskCount() {
    int result = 1;

    for (final BackgroundInitializer<?> bi : childInitializers.values()) {
        result += bi.getTaskCount();
    }

    return result;
}
\end{minted}
    \caption{Method \textit{getVarArgs(Object[], Class$<$?$>$[])} of class
    \textit{reflect.MethodUtils} in Apache Commons Lang 3.12.0.}
    \label{lst:mbi}
\end{listing}

Here, the object pointed by \texttt{childInitializers} is accessed without using
any lock, while other methods of the class use the implicit lock of the instance
(i.e. \mintinline{java}{synchronized(this)}). Simply adding a
\mintinline{java}{synchronized} block around the for loop extinguishes the
warning.

The refactoring performed for all three warnings has not produced further
warnings, and it has not caused the failure of any unit test.

\section{Conclusions}

Given that Apache Commons Lang is a very mature project (the code still contains
workarounds targeting Java 1.3) it is not surprising that Infer has detected a
relatively limited number of warnings. If anything this should be a good
testament to the skills and discipline of all project contributors. However, 3
true positives were found in this production-ready release version. This is a
testament to the insidiousness of some programming mistakes like lack of
defensiveness when dealing with possibly null values and improper use of lock
constructs, a fact which applies to this project as well.

The high false positive ratio of the analysis highlights the tradeoff between
soundness and completeness software analysis tecniques face. Given that the true
positives were quite non-trivial, nevertheless Infer proves itself as a useful
tool even with mature and production-ready software.

To draw some conclusions between this analysis and the one performed last
semester during the SDM class, I hereby compare the current results with the
ones formerly found.

When compared to the PMD source code analyzer and SonarQube, Infer reports
issues closer to external quality factors (i.e. user satisfaction, and
consequently runtime behaviour) rather than internal quality ones, such as the
adherence to code style rules and presence of adequate documentation. 

Some
overlap is present in the scope of the analysis of both tools, namely with
respect to thread safety (and null dereference with SonarQube). It is worth to
note that all three tool reported warnings with distinct locations in the source
code, and no overlap was found between them.

However, due to
its control and data flow analysis capabilities, Infer is a superior tool to
understand and check possible runtime behavior while analyzing only the source
code.

We can also say both PMD and SonarQube have superior awareness regarding the
behaviour of Java and its standard library. For example, they are aware of
boxing and unboxing of primitive types (and SonarQube even produces warnings
about misuse of the feature), where as hinted by this analysis Infer seems not
to be aware of, at least while searching null dereferences.

\end{document}