yellow yellow

#  slash: A Technique for Static Configuration-Logic Identification

Mohannad Alhanahnah  University of Wisconsin-Madison  Philipp Schubert
Paderborn University  Thomas Reps  University of Wisconsin-Madison  Somesh Jha
University of Wisconsin-Madison  Eric Bodden  Paderborn University

###### Abstract

Researchers have recently devised tools for debloating software and detecting
configuration errors. Several of these tools rely on the observation that
programs are composed of an initialization phase followed by a main-
computation phase. Users of these tools are required to _manually_ annotate
the boundary that separates these phases, a task that can be time-consuming
and error-prone. (Typically, the user has to read and understand the source
code or trace executions with a debugger.) Because errors can impair the
tools’ accuracy and functionality, the manual-annotation requirement hinders
the ability to apply the tools on a large scale.

In this paper, we present a field study of 24 widely-used C/C++ programs,
identifying common boundary properties in $96\%$ of them. We then introduce
slash, an automated tool that locates the boundary based on the identified
properties. slash successfully identifies the boundary in $87.5\%$ of the
studied programs within 8.5 minutes, using up to 4.4 GB memory. In an
independent test, carried out after slash was developed, slash identified the
boundary in $85.7\%$ of a dataset of $21$ popular C/C++ GitHub repositories.
Finally, we demonstrate slash’s potential to streamline the boundary-
identification process of software-debloating and error-detection tools.

##  1 Introduction

Software configurability has emerged as a significant focus in contemporary
research [12, 18, 11, 28, 25, 16, 27, 17, 29]. Concurrently, several
initiatives proposed to elevate configurability as a first-class programming
element [5] and aimed to forge consensus and promote best practices [14, 20].
One best practice is to organize programs to operate in two phases: (i) a
phase for _initialization_ , where configuration logic checks parameters and
initializes corresponding values to control the program’s activities, and (ii)
a _main-computation phase_ that performs actions in accordance with the
specified configuration). One would hope that this structure is reflected in
the code—i.e., there is a boundary between the configuration logic and the
main computation. A number of recent papers [2, 6, 26, 7] also describe the
advantages that this separation provides for the sake of configuration
traceability [14], forensic analysis [7], optimizing programs [2, 6], and
detecting configuration errors [26].

PCHECK [26] automatically generates a checker that detects configuration
errors early to minimize damage from failures. It adds a call to the checker
at the end of the initialization phase, as illustrated in Figure 1, which
depicts the boundary location in the program Squid, a widely used open-source
Web proxy server that supports $237$ configurations. However, a user of PCHECK
needs to _manually_ annotate the Squid source code with the boundary location.

The situation is similar for program-debloating tools. Temporal-specialization
[6] disables system APIs after the completion of the initialization phase, but
also requires the tool user to annotate the boundary. LMCAS [2] specializes
programs by executing them up to the boundary to capture the program’s state
according to the supplied inputs, where again the LMCAS user must annotate the
location of the boundary.

figureLocation to invoke the configuration-error checker generated by PCHECK
[26] in Squid—i.e., the boundary at the end of the initialization phase.
PCHECK users need to annotate this location _manually_.

In the absence of a method to assist developers in identifying the boundary,
the manual annotation is a time-consuming and error-prone task: the user has
to read and understand the source code or trace executions with a debugger.
Because boundary-identification errors can impair the tools’ accuracy and
functionality, the manual-annotation requirement hinders the ability to apply
the tools on a large scale.

We thus first conduct a manual field study to comprehend how the boundary is
implemented and to discern its distinguishing characteristics. Our corpus
contains $24$ widely used C/C++ programs (Table 1) that employ configuration
files or command-line parameters. Our study identifies various categories of
boundaries: single-element boundaries, multi-element boundaries, or “blended”
(i.e., no boundary). The study further indicates that 23 (96%) of the programs
possess a single-element boundary. Accordingly, we developed slash, a tool to
identify a boundary automatically. slash focuses on the common case of
identifying a boundary in applications that contain one or more single-element
boundaries. slash analyzes LLVM IR, and targets programs written in an
imperative programming language, such as C or C++.

Our work makes the following contributions:

  1. 1.

We conducted a manual field study to determine (i) to what extent real-world
programs contain a boundary that separates configuration logic from the main-
computation logic, and (ii) for programs that do contain a boundary, what
structural patterns can be used to identify the end of the
initialization/configuration phase (§3).

  2. 2.

We present an algorithm that either identifies a boundary that separates the
initialization and main-computation phases, or reports that it was unable to
do so (§5).

  3. 3.

We implemented the boundary-identification algorithm in a tool, called slash,
and evaluated it on (a) the $24$ programs used in the manual field study, and
(b) $21$ popular C/C++ Github repositories not part of the manual field study
(§6).

  4. 4.

We demonstrate that the boundaries that slash identifies are suitable
substitutes for the ones identified manually (by the respective developers)
for two software-debloating tools [6, 2] and a configuration-error-checking
tool [26].

##  2 Background

This section provides background on some concepts and patterns that we relied
on in our manual field study.

###  2.1 Program Phases

An example of a boundary is shown in Figure 1, which represents a scaled-down
version of the UNIX word-count utility wc: wc reads a line from stdin, counts
the number of lines and/or characters in the input stream, and prints the
results on stdout. This program has two phases, the code for which is found in
disjoint regions:

  * •

The _initialization phase_ starts at the entry point of main (line $1$), and
ends at line $16$.

  * •

The _main-computation phase_ starts at line $18$ and continues to the end of
main (line $28$).

When the configuration logic in the initialization phase is executed, a
parameter expressed in some _external format_ —here argv[1] as a C string—is
translated to an _internal format_ and assigned to one or more program
variables that host run-time configuration data. These variables are known as
_configuration-hosting variables_ [1]. In Figure 1, after the configuration
logic executes, the configuration-hosting variables count_char and count_line
each hold internal-format values of 0 or 1. The main-computation logic then
performs the primary processing function of the program, with its actions
controlled by the values of count_char and count_line.

The two regions are tied together through the values of the configuration-
hosting variables: when the main-computation phase executes, the values of
count_char and count_line control which portions of the main logic execute. In
wc, for instance, count_char controls whether lines $20$ and $24$ execute, and
count_line controls whether lines $21$ and $26$ execute. In wc, there is a
boundary at line $17$ that physically separates the configuration logic from
the main-computation phase.

Figure 1: A scaled-down version of the wc utility. The boundary could be just
before line $17$, just before line $18$, or just before line $19$. LMCAS
executes wc up to the boundary during the course of its analysis but its users
are required to annotate the boundary location _manually_.

###  2.2 Configuration-Logic Phases

To inform the process of identifying a boundary, it is crucial to understand
the configuration logic and patterns inside the initialization phase. We adopt
the taxonomy of configuration design of Zhang et al. [28], which involves the
following configuration phases:

  1. 1.

Parse and Assign: run-time-configuration information is first parsed and
translated. Translated values of configuration parameters are typically
Booleans, integers, or strings. In a command-line program, the inputs are
provided via command-line arguments. In C/C++ programs, command-line arguments
are passed to main() via the parameters argc and argv: argc holds the number
of command-line arguments, and argv[] is an array (of that length) of
pointers; the elements of argv[] point to the different arguments passed to
the program. The application then assigns values of argv[] elements to
configuration-hosting variables according to a predefined argument-value
mapping.

Similar logic is used in configuration-file programs. They also permit
command-line arguments, yet they receive further arguments using configuration
files, whose location is typically provided via one command-line argument. The
configuration file is frequently parsed using a system-call API. For example,
Nginx uses the Linux system call pread, and DNSProxy uses the C library
function fgets. The application then usually assigns configuration-hosting
variables values according to a predefined keyword-value mapping.

  2. 2.

Check and Exception/Error Handling: in general, these steps are intertwined
with the parse-and-assign step. They validate the provided inputs based on
certain constraints, identify incorrect configuration parameters and—if
present—provide user feedback and terminate the program.

Parse-assign-check steps are executed inside a loop until all configuration
parameters are processed or an error arises. Once parameters pass checks, the
main program can utilize these (translated) values to select functionalities.
This processing completion denotes the transition from the initialization to
the main-computation phase.

##  3 Understanding boundary Characteristics

This section describes our manual field study, conducted to determine (i) to
what extent real-world programs contain a boundary that separates
configuration logic from the main-computation logic, and (ii) for programs
that do contain a boundary, what structural patterns exist that could be used
to automate the process of identifying the boundary.

Table 1:  Results of the manual field study. Column $2$ gives LOC (in
thousands), based on readable LLVM IR. Column $3$ indicates whether the
program can receive additional configuration settings through a configuration
file. Column $4$ indicates if there are multiple acceptable (single-element)
boundary locations. Column $5$ specifies whether the location selected based
on our manual inspection (typically the first acceptable boundary location)
lies within or outside main.

Program | kLOC | Config File |  Multiple boundary | Inside main
---|---|---|---|---
End-User Programs
curl-7.47.0 | 31.6 | ✓ | ✓ | ✗
date-8.32 | 56.9 | ✗ | ✗ | ✓
diff-2.8 | 37.2 | ✗ | ✗ | ✓
du-8.32 | 109.1 | ✗ | ✗ | ✓
echo-8.32 | 11.0 | ✗ | ✗ | ✓
gzip-1.2.4 | 26.7 | ✗ | ✓ | ✓
id-8.32 | 15.1 | ✗ | ✗ | ✓
kill-8.32 | 12.1 | ✗ | ✗ | ✓
objdump-2.33 | 1049.0 | ✗ | ✗ | ✓
psql-15 | 189.1 | ✗ | ✓ | ✓
readelf-2.33 | 413.7 | ✗ | ✓ | ✓
sort-8.32 | 55.9 | ✗ | ✗ | ✓
tcpdump-4.10.0 | 608.6 | ✗ | ✗ | ✓
uniq-8.32 | 14.8 | ✗ | ✗ | ✓
wc-8.32 | 17.8 | ✗ | ✓ | ✓
wget-1.17.1 | 165.5 | ✓ | ✓ | ✓
Server Programs
bind-9.15.8 | 1755.1 | ✓ | ✓ | ✓
DNSProxy-1.17 | 3.4 | ✓ | ✓ | ✓
httpd-2.4.51 | 179.0 | ✓ | ✓ | ✓
knockd-0.5 | 10.9 | ✓ | ✓ | ✓
lighttpd-1.4.54 | 174.0 | ✓ | ✗ | ✗
mini-httpd1-1.19 | 16.4 | ✓ | ✗ | ✓
Nginx-1.19.0 | 589.2 | ✓ | ✓ | ✓
PostgreSQL-15 | 4626.3 | ✓ | Multi-element boundary

###  3.1 Methodology

Selection of subject programs. We manually inspected $24$ widely-used [2, 6,
21, 22, 29] end-user and server C/C++ programs, listed in Table 1. The
configurations of these programs are provided either through command-line
arguments or configuration files. The end-user programs include utilities
(i.e., sort, objdump, diff, and gzip). The server programs include web servers
(i.e., Nginx), DNS servers (i.e., DNSProxy), and database programs (i.e.,
PostgreSQL).

Manual-inspection procedure. We manually inspected the source code of the
programs to see if we could identify a boundary location. The inspection was
conducted by one person from our team, but a second opinion was obtained for
challenging cases, such as Nginx, httpd, and PostgreSQL. The manual field
study was performed as follows:

  1. (a)

We built the program and ran it with -help to display all runtime
configuration parameters. For config-file programs, we also inspected the
program’s default configuration-file templates to identify the set of
predefined keywords (e.g., Nginx uses the directive gzip to enable/diable
compression).

  2. (b)

Next, we identified the entry-point function in the source code. Because the
study considered C/C++ programs, we searched for a function named “main” that
has two parameters named “argc” and “argv.”

  3. (c)

We identified the locations in the source code where the configuration
parameters are parsed, assigned, and checked (thereby identifying the
configuration-hosting variables). A regular-expression search (based on the
knowledge gained from step (a) was sufficient for identifying such locations.
We observed that some programs parse the configuration parameters outside of
main; for instance, the main function of a command-line program might invoke
another function and pass argv as a parameter. For configuration-file
programs, we performed a regular-expression search to find (i) method names in
APIs for reading/parsing files, and (ii) keywords used in the configuration
file.

To supplement source-code inspection, we ran the programs with a debugger
(GDB) to track the use of argv and identify the location where the provided
configuration parameters are parsed. Similarly, we ran the configuration-file
programs with GDB by specifying the configuration-file-parsing API as
breakpoints.

  4. (d)

We sought to identify a location for the boundary. We looked to see if the
location just after the end of the loop containing the parse-assign-check
logic was acceptable. In some cases, the boundary location was a bit further
along in the program because the values of configuration-hosting variables are
sometimes set or adjusted after the parse-assign-check loop when one
configuration feature overrides another.

###  3.2 Results

Categories of boundaries. Our study identifies several types of boundaries
within programs:

  * •

Single-element boundaries: one or more sites exist that, individually, are
each an acceptable boundary location (as in wc from Figure 1).

  * •

Multi-element boundaries: No single-element boundary exists, but a collection
of sites separate the program’s configuration logic from the main-computation
phase.

  * •

“Blended” boundaries: the application’s configuration logic is “blended” into
the main-computation phase, yielding no clear boundary of the foregoing two
types.

The manual-field study showed that $23$ programs possess single-element
boundaries. As illustrated in Figure 1, it is possible that there are multiple
locations where a single-element boundary could be located. (The term
“multiple single-element boundaries” should not be confused with “multi-
element boundary”). E.g., in Figure 1 the boundary could be just before line
$17$, just before line $18$, or just before line $19$. Column 4 of Table 1
indicates which of the programs had multiple single-element boundaries. The
remaining program, PostgreSQL (a database server), has a multi-element
boundary. It is a Swiss-Army-knife program, consisting of several stand-alone
programs, each with its own boundary or boundaries.

Table 2: Number of programs in each boundary category.

Dataset | Single-elem. | Multi-elem. | Blended
---|---|---|---
Manual field study | 23 | 1 | 0
Previously unseen | 17 | 1 | 3

The corpus of programs used in the manual field study (Table 1) had no
instances of “blended” boundaries. However, our evaluation dataset of
previously unseen programs (Table 4) contains three programs with “blended”
boundaries. Table 2 shows the numbers of programs in each boundary category.

,

Behaviour of configuration-hosting variables. In $20$ of the $24$ programs,
the values of the configuration-hosting variables are not changed after they
are given values within the parse-assign-check loop. In three cases (tcpdump,
Gzip, and readelf), we observed that feature interactions—in one case,
involving a compile-time configuration feature (#ifdef)—can cause the program
to change the value of a configuration-hosting variable after the parse-
assign-check loop.

Field Study Results: The study revealed that: • $23$ of the $24$ programs have
a single-element boundary that divides the program into its configuration
logic and its main-computation logic. • The assignments to configuration-
hosting variables typically all occur inside a parse-assign-check loop that
processes the command line or configuration file. • Because of interactions
among configuration features, the values of configuration-hosting variables
are sometimes adjusted after the parse-assign-check loop.

###  3.3 Findings: Properties of the boundary

Our study revealed a set of properties that were common across the $23$
programs in which we were able to identify a single-element boundary. We use
these properties in §4 and §5 to address the problem of _automatically_
identifying a suitable single-element boundary location.

The main property that we can infer from Figure 1 is that the boundary divides
a program’s control-flow graph into two disjoint subgraphs. This property
implies that the boundary is a so-called articulation point in the program
(i.e., a vertex cut of the control-flow graph, of size $1$). In addition, we
observed that the boundary should be:

  * •

Reachable from the entry point of the program.

  * •

Executed exactly once, which eliminates the possibility that the boundary is
inside a loop or a conditional statement.

To validate our hypothesis, we instrumented the programs by adding a print
statement at the location where the boundary is identified (e.g., line $17$ in
Figure 1) and then executed the program several times with different sets of
configuration parameters. If the print statement is executed, the run
indicates the boundary is reachable from the entry; if the print statement is
printed only once, the run indicates that the boundary is executed exactly
once (for the given configuration).

In the debugging performed in step c of the manual inspection steps in § 3.1,
we dynamically traced the uses of argv and calls to configuration-file parsing
APIs as a way to pinpoint the locations where configurations are parsed,
assigned, and checked. This use of dynamic tracing of argv during manual
analysis suggests that a technique to identify boundaries automatically will
need to perform dataflow analysis to track uses of argv statically.

Findings: Properties relevant to identifying automatically a program’s
boundary include: 1. Configuration-hosting variables are data dependent or
control dependent on argv. 2. The boundary should be located after at least
one loop. 3. The boundary represents an articulation point in the program’s
control-flow graph. 4. The boundary should be reachable from the entry point
and executed only once.

##  4 The boundary-Identification Problem

This section provides an abstract overview of the boundary concept, presenting
the process of boundary identification as a form of staging transformation
(§4.1). It then defines the boundary-identification task (§4.2 and §4.3).

###  4.1 An Idealized View

At an abstract level, automated boundary identification can be thought of as a
kind of _staging transformation_ [10] that isolates (or “stages”) the
processing of a program’s configuration parameters. Staging transformations
were originally proposed to separate a program’s computation into stages for
optimization purposes. In our context, given a program $P(x)$ with body
$f(x)$, where $x$ represents some configuration parameter, we wish to consider
$P$ as having the form shown below in the second line:

$\begin{array}[]{rr@{\hspace{1.0ex}}c@{\hspace{1.0ex}}l}&P(x)\hskip
4.30554pt&=\hfil\hskip 4.30554pt&f(x)\\\ \rightarrow&P(x)\hskip
4.30554pt&=\hfil\hskip
4.30554pt&\textbf{let}\;t=\textit{translate}(x)\;\textbf{in}\;g(t)\end{array}$
(1)

Here, $\textit{translate}(\cdot)$ converts from the external configuration-
specification format to the internal format, and $t$ is a configuration-
hosting variable. Thus,

  * •

“$\textbf{let}\;t=\textit{translate}(x)\;\textbf{in}\;\ldots$” represents the
configuration logic of $P$.

  * •

“$g(t)$" represents the main logic, which performs the primary processing
function of $P$, based on the value of configuration-hosting variable $t$.

The boundary-identification challenge is to find the code that constitutes
translate within function definition $f$.

This abstract characterization of boundary identification permits giving a
“rational reconstruction” of some previous work. For instance, both PCHECK
[26] and Zhang et al. [28] propose methodologies to ensure that the value of a
configuration parameter is checked against an appropriate constraint
$\varphi(\cdot)$ on the parameter before it is used. Thus, if one has program
$P(x)$ in the form shown on the second line of Eqn. (1), the essence of both
PCHECK and the Zhang et al. paper is to transform $P$ as follows:

$\begin{array}[]{rr@{\hspace{1.0ex}}c@{\hspace{1.0ex}}l}&P(x)\hskip
4.30554pt&=\hfil\hskip
4.30554pt&\textbf{let}\;t=\textit{translate}(x)\;\textbf{in}\;g(t)\\\
\rightarrow&P(x)\hskip 4.30554pt&=\hfil\hskip
4.30554pt&\textbf{let}\;t=\textit{translate}(x)\\\ &\hskip
4.30554pt&\hfil\hskip
4.30554pt&\textbf{in}\;\textbf{if}\;\varphi(t)\;\textbf{then}\;g(t)\;\textbf{else}\;\textbf{abort}\end{array}$
(2)

Furthermore, several issues discussed in [14, 20, 12, 11] can be characterized
as “it is advantageous to separate the configuration logic from the program’s
main-computation logic for the sake of facilitating configuration tracking and
analysis,” which at an abstract level amounts to:

$\begin{array}[]{l}\textit{Given program $P$ in the form}\\\ \qquad
P(x)=\textbf{let}\;t=\textit{translate}(x)\;\textbf{in}\;g(t)\\\
\textit{Analyze the usage of}\,t\;\textit{in}\;g(t)\end{array}$ (3)

For instance, LOTRACK’s usage analysis aims to identify code fragments
corresponding to load-time configurations [12, 11] in Android and Java
programs.

Finally, LMCAS [2] relies on manual techniques to identify a program’s
boundary, and then performs partial evaluation [9] with respect to the values
of configuration-hosting variables. Abstractly, LMCAS operates similarly to
what was discussed above, except that $P$ is now a two-argument program,
$P(x,y)$.

$\begin{array}[]{rr@{\hspace{1.0ex}}c@{\hspace{1.0ex}}l}&P(x,y)\hskip
4.30554pt&=\hfil\hskip
4.30554pt&\textbf{let}\;t=\textit{translate}(x)\;\textbf{in}\;g(t,y)\\\
\rightarrow&P_{x}(y)\hskip 4.30554pt&=\hfil\hskip
4.30554pt&g_{t}(y)\end{array}$ (4)

Program $P_{x}(y)$ is a version of $P(x,y)$ specialized with respect to a
specific value of $x$. The body of $P_{x}(y)$ is obtained by finding and
evaluating $t=\textit{translate}(x)$, and then running a partial evaluator on
$g$ with static input $t$ to create $g_{t}(y)$, which is a version of $g(t,y)$
specialized on the value of $t$.

###  4.2 Terminology and Notation

Because the boundary constitutes an articulation point in the program, we
formulate the boundary-identification task as a vertex-cut graph-partitioning
problem.

###### Definition 1

Let $G=(V,E,{v_{{\textit{en}}}},{v_{{\textit{ex}}}})$ denotes the
Interprocedural Control-Flow Graph (ICFG) of a program $P$. Vertices
${v_{{\textit{en}}}}$ and ${v_{{\textit{ex}}}}$ represent the entry vertex
corresponding to the main and end of the program, respectively.

Without loss of generality, we assume that each vertex in $G$ is reachable
from ${v_{{\textit{en}}}}$ along a path in which each procedure-return edge is
matched with its closest preceding unmatched procedure-call edge (a so-called
“interprocedurally valid path” [24, §7-3]). A vertex $v$ in the control-flow
graph $G_{Q}$ of some procedure $Q$ is said to be an _articulation point_ if
removing $v$, and all control-flow edges into and out of $v$, partitions
$G_{Q}$ into two non-empty subgraphs.

###  4.3 Problem Definition

In the abstract view of the boundary-identification problem discussed in §4.1,
a command-line or configuration-file program $P(x)=f(x)$ has the form shown on
the second line of Eqn. (1).

Eqn. (1) is stated in an abstract form, as if we were considering a program in
a functional programming language. However, we need to translate this idea to
something that is suitable for an imperative programming language, such as
C/C++. In such a case, configuration parameter $x$ will be argv.

Our goal is to identify $\textit{translate}(x)$, whose end is considered to be
the boundary (but in an imperative program), which leaves us with two
questions:

  1. 1.

What is a suitable “choke point” in the program, analogous to the hand-off
from “$t=\textit{translate}(x)$” to $g(t)$ in Eqn. (1)?

  2. 2.

What does “the program has finished $\textit{translate}(x)$” mean?

With respect to question (1), a natural approach is in terms of the
articulation points of the program’s control-flow graph $G$: the candidate
choke points are the articulation points of $G$ (denoted by $V_{AP}$). In
general, $G$ can have many articulation points. We need some other conditions
to specify which member of $V_{AP}$ we want: the boundary separates the
vertices of $G$ into the configuration logic (denoted by $V_{c}$)—which is
analogous to $\textit{translate}(x)$—and vertices belong to the main-
computation logic (denoted by $V_{m}$)—which is analogous to $g(t)$.

With respect to question (2), discovering the end of $\textit{translate}(x)$
entails identifying the _configuration-hosting variables_ [1] (which are
analogous to variable $t$ in Eqn. (1)). These variables are either (a)
assigned configuration values directly, or (b) control dependent on branch
expressions involving configuration quantities. As supported by the findings
from our manual study (§3), the assignments to configuration-hosting variables
(i) typically all occur inside a parse-assign-check loop that processes the
command line or configuration file, but (ii) some additional assignments to
them may occur after the parse-assign-check loop because of interactions among
configuration features. Configuration-hosting variables are typically live
variables in the main logic; moreover, they are used without their values
being modified in the main-computation phase [12, 3]. We formalize this
concept as follows:

Configuration-hosting variables ($C_{\textit{host}}$). 1. Let $v_{x}$ denote
the CFG vertex that models the passing of configuration parameter $x$ to main.
2. Let $V_{\textit{host}}=\\{v_{0},v_{1},\ldots,v_{n}\\}$ denote the set of
vertices that represent assignments to configuration-hosting variables:
$v_{i}\in V_{\textit{host}}$ if (a) $v_{i}$ is flow dependent on $v_{x}$,
denoted by $v_{x}\longrightarrow_{f}v_{i}$, or (b) $v_{i}$ is control
dependent on a vertex $w_{x}$ that uses $x$. 3. The set of configuration-
hosting variables $C_{\textit{host}}$ is the set of variables that are
assigned to at some member of $V_{\textit{host}}$.

For instance, in the scaled-down word-count program in Figure 1, the global
variables count_chars and count_lines are assigned values at lines $6$ and
$9$, respectively; these assignments are control-dependent on vertices that
use argv (i.e., the branch-conditions on lines $3$ and $4$, which play the
role of $w_{x}$ in item (2b)). Thus, by item (2b), $V_{\textit{host}}$
consists of the assignments at lines $6$ and $9$, and by item (3),
$C_{\textit{host}}$ is $\\{\texttt{count\\_chars},\texttt{count\\_lines}\\}$.

With the concept of $C_{\textit{host}}$ in hand, we can now state the
boundary-identification problem.

Problem Definition: Find an articulation point $B$ of CFG $G$ that is
reachable from ${v_{{\textit{en}}}}$, and 1. is located after a loop, 2. post-
dominates every assignment to a member of $C_{\textit{host}}$, and 3. for each
$c\in C_{\textit{host}}$, all paths from $B$ to ${v_{{\textit{ex}}}}$ are free
of definitions to $c$. Return the closest $B$ to the entry as the boundary.

The control-flow vertex for line $16$ of Figure 1 is an articulation point
that meets the conditions of the problem definition:

  * •

it is located after the end of the for-loop on lines $2$-$16$

  * •

it post-dominates every assignment to count_chars and count_lines, and

  * •

all paths from that point to the end of the program are free of definitions to
count_chars and count_lines.

Finally, the articulation point at line $16$ is the closest to the entry point
in terms of distance along control-flow edges.

##  5 Automatic boundary Identification

1

2

Input: Program P, SrcProcedure

Output: boundary

3 Entry point $Entry$ = getEntryPointBasicBlock ($P$)

4 G = computeICFG ($P$)

5 Initalize ConfigHostVars $V_{\textit{host}}$ ,BoundaryCandidates $BC$

/* Identification of boundary Candidates (Section 5.1) */

6 T = computeTaintAnalysis(G, SrcProcedure);

7 foreach  _$node\in G$_ do

8 foreach  _$Res\in T.getTaintResultsAt(node)$_ do

9 foreach  _$Op\in node.operands()$_ do

10 if  _$Op$ = $Res\leavevmode\nobreak\ \land$ isAssignmentInst(_$node$_)_
then

11 $V_{\textit{host}}\ {\cup}{=}\leavevmode\nobreak\ \leavevmode\nobreak\
node.getBasicBlock()$

12

13 if  _$Op$ = $Res\leavevmode\nobreak\ \land$ isControlDependent(_$node$ ,
$Op$_)_ then

14 $V_{\textit{host}}\ {\cup}{=}\leavevmode\nobreak\ $
getAssignmentsIn(_$node.getBasicBlock()$_)

15

16

17

18

19 $C_{\textit{host}}=$ identifyVariablesAssignedToIn(_$V_{\textit{host}}$_)

/* Add a loop’s successors, if $C\in V_{\textit{host}}$ is within a loop */

20 $SCCs=$ computeStronglyConnectedComponents(_$G$_)

21 foreach  _$C\in V_{\textit{host}}$_ do

22 if  _isInLoopStructure(_$C,SCCs$_)_ then

23 $BC\leavevmode\nobreak\ {\cup}{=}$ getLoopExitBlocks(_$C$_)

24

25 else $BC\leavevmode\nobreak\ {\cup}{=}\leavevmode\nobreak\ C$

26

27
$AP=\textnormal{{computeArticulationPoints(}}\textnormal{\emph{G}}\textnormal{{)}}$

28 $BC=BC\cap AP$

29 foreach  _$C\in BC$_ do

30 if  _isReachableFromEntry(_$C$_)_ then

/* Find proxies in main for boundary candidates in other procedures */

31 if  _$C\notin\texttt{main}$_ then

32 foreach  _$\textit{CallSite}\in\texttt{main}$_ do

33 if  _isReachable(_$\textit{CallSite},C$_)_ then

34 $BC=BC\setminus\\{C\\}$

35 $BC\leavevmode\nobreak\ {\cup}{=}\leavevmode\nobreak\
CallSite.getBasicBlock()$

36

37

38

39

40 else $BC=BC\setminus\\{C\\}$

41

$BC=BC\cap AP$

/* Proxies must be articulation points */

/* boundary Identification (Section 5.2) */

42 $DG=$ computePostDominators(_$G$_)

43 foreach  _$C\in BC$_ do

/* C1: Check that boundary is located after a loop */

44 if  _! followsLoop(_$C$_)_ then

45 $BC=BC\setminus\\{C\\}$

46

/* C2: Check whether $C$ post-dominates every assignment $d$ to a var in
$C_{\textit{host}}$ */

47 $\textit{PostDominatesFlag}=true$

48 foreach  _assignment $d$ to a variable in $C_{\textit{host}}$_ do

49 if  _! postDominates(_$DG,C,d.getBasicBlock()$_)_ then

50 $\textit{PostDominatesFlag}=false$

51 $BC=BC\setminus\\{C\\}$

52

53

/* C3: Check for definition-free paths from $C$ to $v_{ex}$ using constant
propagation */

54 if  _PostDominatesFlag_ then

55 foreach  _$var\in C_{\textit{host}}$_ do

56 if  _! isConstant(_$G,var,C,v_{ex}$_)_ then

57 $BC=BC\setminus\\{C\\}$

58

59

60

61

62boundary = closestReachableFromEntry(_$BC$_)

63 if  _$\mbox{{boundary}}=\emptyset$_ then

64 return $null$

65

66else return boundary

67

Algorithm 1 Single-element boundary-identification algorithm.

This section presents our algorithm to solve the boundary-identification
problem defined in §4.3. The algorithm is given as Alg. 1. The discussion of
Alg. 1 is structured in two parts, which correspond to lines 1–1 and 1–1,
respectively.

  * •

Identification of boundary Candidates (§5.1). This phase identifies a set of
boundary candidates, which are a subset of the set of articulation points of
the control-flow graph.

  * •

boundary Identification (§5.2). This phase eliminates all boundary candidates
that do not satisfy the three properties of a boundary given in the problem
definition in §4.3.

###  5.1 boundary Candidates (Lines 1–1)

This phase performs taint analysis and control-flow analysis to identify a set
of boundary candidates. It performs taint analysis to identify the set of
configuration-hosting variables $C_{\textit{host}}$ and the set of assignments
$V_{\textit{host}}$ defined in §4.3 (lines 1–1). Some adjustments are made
when the latter assignments are either inside a loop (lines 1–1), or in a
procedure other than main (lines 1–1). In particular, for each candidate not
in main, a proxy location is considered just after the appropriate call in
main that would reach the candidate.

The algorithm performs control-flow analysis to identify the set of
articulation points in $G$ (line 1). The outcome of this phase is the
intersection between the set of articulation points and the (adjusted) set of
vertices that represent assignments to configuration-hosting variables (first
performed at line 1 to reduce the cost of the proxy-finding loop, then at line
1).

###  5.2 boundary Identification (Lines 1–1)

This phase eliminates all boundary candidates that do not satisfy the three
conditions of a boundary given in the problem definition in §4.3, namely, each
$C\in BC$ must (C1) be located after a loop, (C2) post-dominate every
assignment to a member of $C_{\textit{host}}$, and (C3) for each
$\textit{var}\in C_{\textit{host}}$, all paths from $B$ to
${v_{{\textit{ex}}}}$ are free of definitions to var. The algorithm removes
from $BC$ any vertex $C$ that fails to satisfy all three conditions; see lines
1–1, 1–1, and 1–1, respectively.

To verify condition (C1), the algorithm checks whether candidate $C\in BC$ is
located after a loop (lines 1-1). To verify condition (C3), the algorithm can
use standard techniques—e.g., IFDS-based [19], inter-procedural constant
propagation for each configuration-hosting variable var, starting at candidate
$C\in BC$. If the analysis reports that var is not constant at exit point
${v_{{\textit{ex}}}}$, then var might be (re)defined on some path from $C$ to
${v_{{\textit{ex}}}}$, and hence condition (C3) is violated.

This phase returns null if all boundary candidates are eliminated (lines 1–1);
otherwise, it returns the candidate that is closest to ${v_{{\textit{en}}}}$,
the entry point of procedure main (lines 1 and 1). The distance metric used to
calculate the closest boundary candidate is the shortest path in terms of
control-flow edges.

###  5.3 Discussion

Limitations. Alg. 1 gives an idealized algorithm that works on an ICFG, yet
slash operates on the ICFG only partially. Specifically, for (a) finding post-
dominators, and (b) finding articulation points our implementation works on
individual CFGs in a procedure-by-procedure manner. Listing LABEL:lst:intra
sketches this variant:

⬇

$AP,\leavevmode\nobreak\ DTs:=\emptyset;$

foreach procedure P {

$DTs:=DTs\leavevmode\nobreak\ \leavevmode\nobreak\ \cup$
computePostDominators(CFG(P))

$AP:=AP\leavevmode\nobreak\ \leavevmode\nobreak\ \cup$
computeArticulationPoints(CFG(P)) }

Listing 1: Variant of computePostDominators and computeArticulationPoints used
in our implementation of Algorithm 1

Consequently, when a boundary candidate is located in some procedure p other
than main, the candidate is relocated to the CFG of main by finding a proxy
location for the candidate. We use the basic block of main that contains the
call site that calls p (directly or transitively).

A second limitation of slash is that it targets only single-element
boundaries. When run on a multi-element-boundary program, it could either
return the empty set (a correct answer with respect to the question of whether
a single-element boundary exists) or some singleton set (which is a false
positive). (In the latter case, our experience is that slash returns one of
the elements of the multi-element boundary, and the rest of the elements are
other boundary candidates.) When run on a program in the “blended”-boundary
case, slash returns the empty set (correct with respect to the question of
whether a single-element boundary exists). In this case, it never returns a
singleton set because the intertwining of the configuration logic and the
main-computation logic causes the properties required of a single-element
boundary to be violated.

Time Complexity. The overall worst-case running time of the algorithm is
bounded by $\mathcal{O}(|E|\cdot|D|^{3}+|N|^{2}+|E|)$, where $N$ and $E$ are
the sets of nodes and edges, respectively, of the program’s ICFG, and $D$ is
the domain(s) used in the data-flow problems (taint analysis and constant
propagation) [19].

##  6 Evaluation

Our experiments were designed to answer three questions:

  * •

RQ1: Can slash identify the boundary location correctly for command-line and
configuration-file programs? (§6.1 shows that slash can identify the
presence/absence of the boundary for $87.5\%$ of the programs in the field
study and for $85.7\%$ of the programs in a previously unseen dataset.)

  * •

RQ2: How expensive is slash in terms of running time and memory usage? (§6.2
reports that total analysis time on $23$ apps is $8.5$ minutes, with max.
memory consumption of $4.4$GB.)

  * •

RQ3: Can slash alleviate the manual efforts required to use existing
debloating tools? (§6.3 demonstrates that slash’s integration with two
debloating tools eliminates a user-annotation requirement without breaking
their functionality.)

The evaluations were carried out on an Ubuntu $16.04$ PC with an Intel
i7-5600U CPU @ 2.6GHz and $16$ GB RAM.

Table 3:  Results of slash’s evaluation. Columns $3$ & $4$ represent the
number of pointers and allocation sites, respectively. Column $5$ indicates
whether slash could identify the boundary location correctly. (“✗ (✓)” means
that slash did not succeed “out of the box,” but was successful when provided
with suitable stubs for two library functions.) Column $6$ specifies slash’s
average running time in seconds, and column $7$ indicates the maximum amount
of memory usage in MB (both over 10 runs).

Program | kLOC | #ptr | #alloc |  Correct boundary |  Analysis Time | Memory
---|---|---|---|---|---|---
End-user Programs
curl-7.47.0 | 31.6 | 10228 | 785 | ✗ | 119.6 | 1526
date-8.32 | 56.9 | 7613 | 979 | ✓ | 26.9 | 698
diff-2.8 | 37.2 | 5331 | 842 | ✓ | 2.9 | 213
du-8.32 | 109.1 | 19168 | 2756 | ✓ | 3.5 | 299
echo-8.32 | 11.0 | 1687 | 305 | ✓ | 0.5 | 72
gzip-1.2.4 | 26.7 | 2952 | 420 | ✓ | 0.6 | 112
id-8.32 | 15.1 | 2368 | 418 | ✓ | 1.8 | 135
kill-8.32 | 12.1 | 1819 | 348 | ✓ | 1.7 | 130
objdump-2.33 | 1049.0 | 209651 | 21984 | ✓ | 37.7 | 1261
psql-15 | 189.1 | 37921 | 3798 | ✓ | 7.4 | 305
readelf-2.33 | 413.7 | 76842 | 8325 | ✓ | 4.5 | 400
sort-8.32 | 55.9 | 9902 | 1549 | ✓ | 4.0 | 254
tcpdump-4.10.0 | 608.6 | 152999 | 11945 | ✓ | 24.1 | 1431
uniq-8.32 | 14.8 | 2340 | 442 | ✓ | 1.9 | 136
wc-8.32 | 17.8 | 3000 | 509 | ✓ | 1.8 | 138
wget-1.17.1 | 165.5 | 30069 | 4036 | ✓ | 2.7 | 276
Server Programs
bind-9.15.8 | 1755.1 | 326408 | 41391 | ✓ | 228.8 | 4292
DNSProxy-1.17 | 3.4 | 583 | 79 | ✓ | 0.1 | 53
httpd-2.4.51 | 179.0 | 75032 | 6927 |  ✗ (✓) | 2.2 | 278
knockd-0.5 | 10.9 | 2062 | 177 | ✓ | 0.1 | 57
lighttpd-1.4.54 | 174.0 | 34932 | 3527 | ✓ | 1.7 | 195
mini-httpd1-1.19 | 16.4 | 2935 | 323 | ✓ | 1.9 | 147
Nginx-1.19.0 | 589.2 | 116710 | 9307 | ✓ | 32.7 | 1232
PostgreSQL-15 | 4626.3 | 880507 | 126401 | ✗ | 575.6 | 8313.7

###  6.1 RQ1: Accuracy of slash

The accuracy of slash is defined as its ability to determine whether the
subject program contains an acceptable single-element boundary. A correct
answer means that slash identified one of the suitable boundary locations, or
correctly indicated that the program lacks any suitable location.

We conducted our evaluation using two sets of programs: (i) the programs
considered in the manual field study (§3, Table 1), and (ii) the $21$ programs
listed in Table 4, which were neither involved in the manual field study nor
examined to determine boundary properties. The latter set was introduced to
provide an unbiased test of accuracy results.

Table 4:  Results of slash’s evaluation based on the previously unseen
programs. Popularity is based on the number of stars. Column 5 reports the
boundary type based on the manual inspection of the source code. Column 6
indicates the outcome of slash’s analysis: (P) means a boundary is present;
(A) (for “absent”) indicates that no boundary is present.

Repo (Program) | Category | Popularity | kLOC |  boundary Type | slash Results | Accuracy
---|---|---|---|---|---|---
AFLplusplus(afl-fuzz) | Software Testing | 3.7k | 164.9 | Single | P | ✓
blurhash(blurhash_encoder) | Image Processing | 13.8k | 58.6 | Blended | A | ✓
Caffe(caffe) | Machine Learning | 33.5k | 17.2 | Blended | A | ✓
fish-shell(fish) | Utility | 21.8k | 696.3 | Single | P | ✓
coreutils(chown) | Utility | 3.5k | 3.37 | Single | P | ✓
coreutils(rm) | Utility | 3.5k | 3.4 | Single | P | ✓
GoAccess(goaccess) | Web | 16.4k | 189.7 | Single | P | ✓
hashcat(hashcat) | Utility | 17.4k | 978 | Single | P | ✓
jq(jq) | Utility | 25.3k | 300.1 | Single | P | ✓
masscan(masscan) | network | 21.3k | 223 | Single | P | ✗
memcached(memcached) | Data | 12.6k | 73.1 | Single | P | ✓
$n^{3}$(nnn) | Data | 16.4k | 46.4 | Single | P | ✓
Redis(redis) | Data | 60k | 1437.4 | Single | OOM | OOM
rethinkdb(rethinkdb) | Data | 26.2k | 839.1 | Multi-element | P | ✗
skynet(skynet) | Games | 12k | 629.7 | Blended | A | ✓
Tesseract(tesseract) | Image Processing | 51.9k | 2204.6 | Single | P | ✓
the_silver_searcher(ag) | Utility | 25k | 28.2 | Single | P | ✓
tmux(tmux) | Utility | 29.5k | 593.6 | Single | P | ✓
trojan(trojan) | Network | 17.8k | 346.6 | Single | P | ✓
twemproxy(nutcracker) | Network | 11.8k | 152.8 | Single | P | ✓
wrk(wrk) | Web | 34.5k | 1203.3 | Single | P | ✓

####  6.1.1 Accuracy based on Manual-Field-Study Dataset

For each program in the evaluation dataset, we measured the accuracy of slash
in identifying the correct boundary location using the following methodology:

  1. 1.

Manually annotate the target program’s source code with the (single-element)
boundary location that is closest to the entry point of main in terms of
distance along control-flow-graph edges, and generate the LLVM IR bitcode.
This information serves as ground truth.

  2. 2.

Pass an un-annotated LLVM IR bitcode of the same target program to slash,
which annotates one basic block of the bitcode as the boundary.

  3. 3.

Check whether the basic block identified by slash matches the ground truth. If
the check passes, then slash is successful in identifying the boundary.

slash accurately reports the existence/absence of an acceptable boundary for
$21$ out of $24$ programs ($87.5\%$) in Table 3. slash fails to report an
accurate boundary location for curl, httpd, and PostgreSQL because of the
following reasons:

  * •

_A Swiss-army-knife program_ : as mentioned in §3, PostgreSQL requires a
multi-element boundary. While this category is not within the purview of the
slash, we still ran slash on PostgreSQL. slash was able to correctly identify
the entire set of elements of the multi-element boundary as boundary
candidates, but returned the one nearest to the program entry point as per
line 1 of Alg. 1.

  * •

_Definitions of two argument-parsing functions are unavailable_ : httpd uses
libapr (Apache Portable Runtime) (specifically apr_getopt_init and apr_getopt)
to parse command-line arguments. Only the declarations of these functions
exist in the LLVM bitcode; their definitions are not available, which prevents
slash from performing taint analysis—and thus from identifying the correct
boundary location. However, when provided with suitable stubs—i.e., taint-
analysis summaries that describe the dependencies of outputs on inputs in
apr_getopt_init and apr_getopt—slash is able to identify the boundary location
correctly.

  * •

_Configuration logic and main-computation phase in the same procedure called
from main_: slash always places the boundary inside main, just after the call
site that contains the code identified as the configuration logic. However, in
curl both the configuration logic and the main-computation logic reside in the
same callee of main. slash is unable to identify the boundary correctly
because no location in main separates the configuration logic from the main-
computation logic.

####  6.1.2 Accuracy based on Previously Unseen Programs

This dataset contains programs that were not employed to deduce the boundary’s
traits (§3).

Selection of Subject Programs. This dataset was acquired by cloning starred
C/C++ projects from GitHub with $3k$ stars or more, which yielded $100$
repositories. We then excluded repositories that (a) include other programming
languages (such as Python, JavaScript, etc.), (b) incorporate GUI
functionality, (c) did not contain an entry point (i.e., firmware), or (d) did
not build successfully. This process yielded the $21$ repositories listed in
Table 4. Of these repositories, $18$ possess a single-element boundary, one
has a multi-element boundary, and two lack any boundary (see Table 2). These
findings corroborate the outcomes of the field study (§3).

For each program in the unseen dataset, we assessed the accuracy of slash
using the following approach:

    1. 1.

Generate the LLVM IR bitcode (without any instrumentation) and analyze it
using slash.

    2. 2.

Manually examine the source code to compare with slash’s outcome. slash’s
result is considered correct if (i) the boundary identified by slash aligns
with the manually identified location, or (ii) slash does not detect any
boundary and the manual inspection confirms the absence of an acceptable
single-element boundary (i.e., the program has multi-element boundaries or no
boundary).

Table 4 presents the boundary-identification results for the unseen programs.
For $18$ out of the $21$ programs, slash accurately reports the
existence/absence of an acceptable (single-element) boundary.

The three cases for which slash reported an inaccurate result were as follows:

  * •

_rethinkdb_ : slash returns a single location in main, rather than a set of
locations that constitute a multi-element boundary.

  * •

_masscan_ : Although the identified boundary satisfies all boundary
properties, the code before this boundary does not actually parse the
configurations. Instead, it configures the program to report debug information
in case it crashes. A single variable, is_backtrace, is initialized inside a
loop that parses argv, whereas the rest of the configuration-hosting variables
are parsed inside another loop inside the function masscan_command_line, which
is called from main. slash does mark the latter location as a candidate
boundary initially, but it is then eliminated because it is not the closest to
the entry of main (line 1 of Alg. 1).

  * •

_Redis_ : Despite running on a server with 192GB of memory, slash’s data-flow
analysis phase exhausted memory.

###  6.2 RQ2: Performance of slash

|
---|---
Figure 2: Lines of code versus time (left) and memory (right).

We measured the analysis time and memory usage for each program in Table 3
(averaged over 10 runs) using the UNIX time tool, which provides the total
analysis time and the peak memory usage that a process uses. As shown in Fig.
2, analysis times and memory consumption scale roughly linearly with lines of
code. (In both plots, the outliers are curl and bind on the high side and
readelf and objdump on the low side.)

slash’s taint analysis is influenced by a program’s characteristics, such as
the number of pointer variables (both # of pointer variables declared and # of
statements that use a pointer variable), stores/loads, indirect call sites,
etc. [22, 23], which affect the number of data-flow facts that need to be
propagated through the target program and are not strictly linked to the
number of lines of code. Table 3 provides information about the number of
pointers and allocation sites in each program. We calculated the Pearson
Correlation Coefficient to establish the strength of the relationship between
kLOC, number of pointers, allocation sites, analysis time, and memory usage.
The Correlation Coefficient in general was over $0.95$, which indicates a
positive linear relationship between these factors.

###  6.3 RQ3: Effectiveness of slash

We discuss three case studies to demonstrate the benefits of integrating slash
in state-of-the-art software-debloating tools [2, 6] and configuration-error
detection tools [26]. The case studies explain how the integration of slash
with these tools alleviates the manual effort required by a developer, thus
making the tools easier to use. These tasks involve combing through source
code to track argc and argv usage, and potentially debugging complex programs
to ensure the boundary is reachable from the program’s entry point.

####  6.3.1 Integration with LMCAS

LMCAS [2] is a debloating tool that applies partial evaluation to specialize a
program to a particular run-time configuration. Currently, the LMCAS user is
required to annotate the program to specify the boundary.

We incorporated slash into the LMCAS pipeline: a program’s LLVM IR bitcode is
annotated by slash with the program’s boundary location, and then passed to
LMCAS. We evaluated our extension of LMCAS on the programs (obtained from the
LMCAS dataset) listed in Table 5. Our aim was to understand the efficiency
gained by integrating slash into LMCAS. Improved efficiency means (1) reducing
or eliminating the burden on the LMCAS user of identifying a program’s
boundary location, and (2) making sure that automatic boundary identification
does not affect LMCAS’s ability to create a correctly working debloated
program. Correct functionality can be validated by running the debloated
programs with the supplied test inputs, omitting the flags specifying the
features for which they have been debloated. We matched the output of the
debloated program with that of the original program, which was supplied the
appropriate feature flags and the same inputs. If the output is the same, the
debloated program is considered to have preserved the functionality. We also
check that the slash-annotated programs do not crash the LMCAS debloating
pipeline.

Table 5 reports the results of this experiment. slash reduces the analysis
time of the boundary-identification step in LMCAS from minutes to a few
seconds. It also eliminates human error due to manual analysis. Finally, slash
\+ LMCAS preserves the functionality of debloated programs (and slash does not
break the debloating pipeline of LMCAS).

Table 5:  Effectiveness of slash in facilitating boundary-identification for
LMCAS.

Program |  boundary ident. time |  Correct boundary |  Functionality Preserved
---|---|---|---
LMCAS (minutes)a |  slash (seconds)
chown | 5 - 10 | 0.6 | ✓ | ✓
date | 5 - 10 | 1.8 | ✓ | ✓
gzip | 5 - 10 | 0.3 | ✓ | ✓
rm | 5 - 10 | 0.7 | ✓ | ✓
sort | 5 - 10 | 1.4 | ✓ | ✓
uniq | 5 - 10 | 0.4 | ✓ | ✓

  * a

Reported by the LMCAS authors [2].

####  6.3.2 Integration with Temporal Specialization

The temporal-specialization tool [6] reduces the attack surface of a server
program by disabling unneeded system calls. The system calls to disable are
determined by splitting server programs into phases of initialization and
serving: any system call never used in the serving phase is to be disabled
once the (manually identified) “transition point” between the phases is
reached. Clearly, a transition point is the same concept as a boundary, so
slash can be applied to the problem of transition-point identification. The
functions for the initialization and serving phases are called the _master_
and _worker_ , respectively. Our evaluation tested whether the function calls
representing each phase are correctly separated. We performed the following
steps: (i) for each program in Table 6 (obtained from the temporal-
specialization dataset), we ran slash to identify the boundary; (ii) as ground
truth, we used the master and worker functions employed in the temporal-
specialization evaluation: If the configuration logic identified by slash
includes a call to the master function, and the main-computation logic
identified by slash contains a call to the worker function, we considered
slash to have identified an appropriate transition point. As shown in Table 6,
slash identified an appropriate transition point in each example, except for
Redis, where the analysis again ran out of memory (OOM).

Table 6:  Effectiveness of slash in facilitating transition-point identification for the temporal-specialization tool. Program |  Correct boundary |  Master func. in config. logic |  Worker func. in main logic
---|---|---|---
Bind | ✓ | ✓ | ✓
Memcached | ✓ | ✓ | ✓
Nginx | ✓ | ✓ | ✓
Apache | ✓ | ✓ | ✓
Lighttpd | ✓ | ✓ | ✓
Redis | OOM | OOM | OOM

####  6.3.3 PCHECK

PCHECK is an analysis tool that aims to detect configuration errors. It
generates configuration-checking code to be invoked after program
initialization. PCHECK requires users to identify the boundary manually.

We could not integrate slash with PCHECK because its implementation is
unavailable. PCHECK’s dataset includes three Java and three C/C++ programs,
but the only boundaries defined in the paper are for Squid (C++) and HDFS
(Java). Thus, we focused our attention on Squid (786k LOC). slash successfully
identified Squid’s boundary in 41 seconds.

##  7 Threats to Validity

We outline threats to the validity of our approach, along with the applied
mitigations:

  * •

Scope of the study (Internal & external validity). We investigated programs
whose configurations are provided through command-line input or configuration
files. Some of our findings may not generalize to other kinds of software,
such as event-driven programs (e.g., Android programs). For the field study,
we selected a diverse set of widely used, mature programs. However, to avoid
bias, we evaluated slash using popular programs from GitHub that we had _not_
used to identify boundary properties.

  * •

Robustness of boundary properties (External validity). The properties used by
slash to infer boundary locations were inferred from the 24 programs in Table
1. Moreover, the properties used by slash do not depend on heuristics like
function/variable names and data types like int/string. slash also does not
exploit special idioms that are used by some programmers for parsing programs’
configurations. For instance, we observed that the GNU Coreutils programs use
a particular idiom (i.e., the invocation of the function getopt_long inside a
while-loop) for parsing command-line parameters. Instead, we decided to have
slash rely on high-level structural properties that are driven by program-
configuration semantics. The evaluation of $21$ unseen programs validates the
identified boundary properties in common programs and confirms slash’s
effectiveness in boundary identification.

  * •

Incorrect propagation of data flows (External Validity). Our taint analysis,
discussed in §5.1, is sound under practical assumptions, such as system and
llibC calls behaving as expected. It does not account for lsetjmp and llongjmp
usage or dynamically loaded code via dlopen/dlsym. If these assumptions are
violated, the analysis becomes unsound.

Finally, there is the question of the soundness slash’s results when run on
the three different kinds of boundary cases.

  * •

Single-element: masscan shows that slash is fallible, and can return an
incorrect answer when a single-element boundary exists (see §6.1.2). The
masscan result constitutes both a false positive and a false negative.

  * •

Multi-element: in our limited experience, slash identifies the locations of a
multi-element boundary as (individual) candidates, but because slash returns
just a singleton location in main, the answer returned is a false positive.

  * •

Blended: slash returns null, because the “blended” case involves violations of
single-element-boundary properties.

##  8 Related Work

Multi-cut for Program Decomposition. Multi-cut algorithms [4] have been used
in several program-optimization methods [8, 15, 13]. Ma et al. [13] presented
a vertex-cut framework on LLVM IR graphs to partition coarse-grained dataflow
graphs into parallel clusters to improve performance of applications in multi-
core systems. In our work, only a degenerate form of min-cut is used: the
algorithm identifies the set of articulation points, each member of which
constitutes a cut-set of size $1$. However, slash’s static taint analysis is
an improvement on the data-dependency analysis used in [13], which relies on
dynamically generated traces.

Tracing Program Configurations. LOTRACK [12, 11] applies taint analysis for
identifying all code that is influenced by load-time configurations in Android
and Java programs. In Android applications, the identification of a boundary
appears to be less of a problem: because Android apps, essentially plugins
with a specific lifecycle in the Android framework, usually have their
configuration logic completed (i.e., typically inside onCreate and before
onStart) by the time of executing their main activity. Hence, this program
point can thus serve as the boundary. This observation does not hold for
regular Java programs, then we foresee slash can be leveraged to solve this
boundary identification challenge in this context. Finally, LOTRACK relies on
the assumption that configuration APIs are known; however, identifying such
APIs can be cumbersome. slash does not require configuration APIs, the taint
analysis of argv is sufficient to identify configuration-hosting variables
including APIs that read configuration files.

##  9 Conclusions and Future Work

This paper presents an algorithm and tool, called slash, to statically
identify programs’ configuration logic. Our evaluation on widely used C/C++
command-line and configuration-file programs confirmed the existence of a
boundary and found that slash _automatically_ identified a suitable boundary
for $87.5\%$ of the programs. Finally, we demonstrated an application of slash
to reduce the manual-annotation burden in software-debloating and error-
detection tools.

Additionally, we envision that slash can be used as a linting tool to alert
developers that they have intertwined a program’s configuration logic with its
main-computation logic. Thus, slash supports ongoing initiatives [5] to
promote configurability as a first-class programming concept.

In future work, we would like to examine the existence of boundaries in GUI
programs and event-driven programs. Furthermore, multi-cut algorithms could
allow slash to handle Swiss-Army-knife cases.

## References

  * [1] Aatira Anum Ahmad, Abdul Rafae Noor, Hashim Sharif, Usama Hameed, Shoaib Asif, Mubashir Anwar, Ashish Gehani, Junaid Haroon Siddiqui, and Fareed M Zaffar.  Trimmer: An automated system for configuration-based software debloating.  IEEE Transactions on Software Engineering, pages 1–1, 2021.
  * [2] Mohannad Alhanahnah, Rithik Jain, Vaibhav Rastogi, Somesh Jha, and Thomas Reps.  Lightweight, multi-stage, compiler-assisted application specialization.  In 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P), pages 251–269, 2022.
  * [3] Florian Angerer, Andreas Grimmer, Herbert Prähofer, and Paul Grünbacher.  Configuration-aware change impact analysis.  In Proceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering, ASE ’15, page 385–395. IEEE Press, 2015.
  * [4] Julia Chuzhoy and Sanjeev Khanna.  Polynomial flow-cut gaps and hardness of directed cut problems.  J. ACM, 56(2), apr 2009.
  * [5] Paul Gazzillo and Myra B. Cohen.  Bringing together configuration research: Towards a common ground.  In Proceedings of the 2022 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, Onward! 2022, page 259–269, New York, NY, USA, 2022. Association for Computing Machinery.
  * [6] Seyedhamed Ghavamnia, Tapti Palit, Shachee Mishra, and Michalis Polychronakis.  Temporal system call specialization for attack surface reduction.  In 29th USENIX Security Symposium (USENIX Security 20), pages 1749–1766. USENIX Association, August 2020.
  * [7] Muhammad Adil Inam, Wajih Ul Hassan, Ali Ahad, Adam Bates, Rashid Tahir, Tianyin Xu, and Fareed Zaffar.  Forensic Analysis of Configuration-based Attacks.  In Proceedings of the 29th Network and Distributed System Security Symposium (NDSS’22), February 2022.
  * [8] Troy A. Johnson, Rudolf Eigenmann, and T. N. Vijaykumar.  Min-cut program decomposition for thread-level speculation.  In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI ’04, page 59–70, New York, NY, USA, 2004. Association for Computing Machinery.
  * [9] Neil D. Jones, Carsten K. Gomard, and Peter Sestoft.  Partial Evaluation and Automatic Program Generation.  Prentice-Hall, Inc., USA, 1993.
  * [10] Ulrik Jørring and William L. Scherlis.  Compilers and staging transformations.  In Proceedings of the 13th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL ’86, page 86–96, New York, NY, USA, 1986. Association for Computing Machinery.
  * [11] Max Lillack, Christian Kästner, and Eric Bodden.  Tracking load-time configuration options.  In Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering, ASE ’14, page 445–456, New York, NY, USA, 2014\. Association for Computing Machinery.
  * [12] Max Lillack, Christian Kästner, and Eric Bodden.  Tracking load-time configuration options.  IEEE Transactions on Software Engineering, 44(12):1269–1291, 2018\.
  * [13] Guixiang Ma, Yao Xiao, Theodore L. Willke, Nesreen K. Ahmed, Shahin Nazarian, and Paul Bogdan.  A vertex cut based framework for load balancing and parallelism optimization in multi-core systems.  CoRR, abs/2010.04414, 2020.
  * [14] Jens Meinicke, Chu-Pan Wong, Bogdan Vasilescu, and Christian Kästner.  Exploring differences and commonalities between feature flags and configuration options.  In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering: Software Engineering in Practice, ICSE-SEIP ’20, page 233–242, New York, NY, USA, 2020. Association for Computing Machinery.
  * [15] Kanemitsu Ootsu, Takeshi Abe, Takashi Yokota, and Takanobu Baba.  Loop performance improvement for min-cut program decomposition method.  In 2010 First International Conference on Networking and Computing, pages 78–87, 2010.
  * [16] Ariel Rabkin and Randy Katz.  Static extraction of program configuration options.  In Proceedings of the 33rd International Conference on Software Engineering, ICSE ’11, page 131–140, New York, NY, USA, 2011. Association for Computing Machinery.
  * [17] Ariel Rabkin and Randy Katz.  Static extraction of program configuration options.  In Proceedings of the 33rd International Conference on Software Engineering, pages 131–140, 2011.
  * [18] Elnatan Reisner, Charles Song, Kin-Keung Ma, Jeffrey S. Foster, and Adam Porter.  Using symbolic evaluation to understand behavior in configurable software systems.  In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1, ICSE ’10, page 445–454, New York, NY, USA, 2010. Association for Computing Machinery.
  * [19] Thomas Reps, Susan Horwitz, and Mooly Sagiv.  Precise interprocedural dataflow analysis via graph reachability.  In Proceedings of the 22Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’95, pages 49–61, New York, NY, USA, 1995. ACM.
  * [20] Mohammed Sayagh, Noureddine Kerzazi, Bram Adams, and Fabio Petrillo.  Software configuration engineering in practice interviews, survey, and systematic literature review.  IEEE Transactions on Software Engineering, 46(6):646–673, 2020\.
  * [21] Philipp Dominik Schubert, Ben Hermann, and Eric Bodden.  Phasar: An inter-procedural static analysis framework for c/c++.  In Tomáš Vojnar and Lijun Zhang, editors, Tools and Algorithms for the Construction and Analysis of Systems, pages 393–410, Cham, 2019. Springer International Publishing.
  * [22] Philipp Dominik Schubert, Richard Leer, Ben Hermann, and Eric Bodden.  Know your analysis: How instrumentation aids understanding static analysis.  In Proceedings of the 8th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis, SOAP 2019, page 8–13, New York, NY, USA, 2019. Association for Computing Machinery.
  * [23] Philipp Dominik Schubert, Richard Leer, Ben Hermann, and Eric Bodden.  Into the woods: Experiences from building a dataflow analysis framework for c/c++.  In 2021 IEEE 21st International Working Conference on Source Code Analysis and Manipulation (SCAM), pages 18–23, 2021.
  * [24] M. Sharir and A. Pnueli.  Two approaches to interprocedural data flow analysis.  In Program Flow Analysis: Theory and Applications. Prentice-Hall, 1981.
  * [25] Tianyin Xu, Long Jin, Xuepeng Fan, Yuanyuan Zhou, Shankar Pasupathy, and Rukma Talwadker.  Hey, you have given me too many knobs!: Understanding and dealing with over-designed configuration in system software.  In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, page 307–319, New York, NY, USA, 2015\. Association for Computing Machinery.
  * [26] Tianyin Xu, Xinxin Jin, Peng Huang, Yuanyuan Zhou, Shan Lu, Long Jin, and Shankar Pasupathy.  Early detection of configuration errors to reduce failure damage.  In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 619–634, Savannah, GA, November 2016. USENIX Association.
  * [27] Sai Zhang and Michael D Ernst.  Which configuration option should i change?  In Proceedings of the 36th International Conference on Software Engineering, pages 152–163, 2014.
  * [28] Yuanliang Zhang, Haochen He, Owolabi Legunsen, Shanshan Li, Wei Dong, and Tianyin Xu.  An evolutionary study of configuration design and implementation in cloud systems.  In 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE), pages 188–200. IEEE, 2021.
  * [29] Shulin Zhou, Xiaodong Liu, Shanshan Li, Wei Dong, Xiangke Liao, and Yun Xiong.  Confmapper: Automated variable finding for configuration items in source code.  In 2016 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C), pages 228–235, 2016.


# Magnetic properties of a spin-3 Chromium condensate

Liang He and Su Yi  Key Laboratory of Frontiers in Theoretical Physics,
Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190,
China

###### Abstract

We study the ground state properties of a spin-3 Cr condensate subject to an
external magnetic field by numerically solving the Gross-Piteavskii equations.
We show that the widely adopted single-mode approximation is invalid under a
finite magnetic field. In particular, a phase separation like behavior may be
induced by the magnetic field. We also point out the possible origin of the
phase separation phenomenon.

###### pacs:

03.75.Mn, 03.75.Hh

##  I Introduction

Since the realization of Bose-Einstein condensate of chromium atoms Pfau05 ,
there have been considerable experimental and theoretical efforts in exploring
physical properties of chromium condensates. Owing to the large magnetic
dipole moment of chromium atoms, the dipolar effects was first identified
experimentally from its expansion dynamics stuh . More remarkably, with the
precise control of the short-range interaction using Feshbach resonance, the
$d$-wave collapse of a pure dipolar condensate has been observed laha .

In the context of spinor condensates, chromium atom has an electronic spin
$s=3$, which provides an ideal platform for exploring even richer quantum
phases as compared to those offered by the spin-1 and spin-2 atoms Ho98 ;
Ohmi98 ; Law98 ; Ciobanu00 ; Koashi00 ; Stenger1998 ; Barret01 ;
Schmaljohann04 ; Chang04 ; Kuwamoto04 . To date, theorists have mapped out the
detailed phase diagram of a spin-3 chromium condensate Santos06 ; Ho06 ;
Makela07 . In particular, a more exotic biaxial nematic phase was also
predicted Ho06 . The possible quantum phases and defects of spin-3 condensates
were also classified based on the symmetry considerations barnett ; yip .
Other work on spin-3 chromium condensates includes theoretically studying the
strongly correlated states of spin-3 bosons in optical lattices bernier  and
the Einstein-de Haas effect in chromium condensates Santos06 ; Ueda .

Nevertheless, all the previous work concerning the ground state and the
magnetic properties of spin-3 Cr condensates has adopted the so-called single-
mode approximation (SMA), which assumes that all spin components share a
common density profile. However, the studies on spin-1 case show that, for an
antiferromagnetic spinor condensate, SMA is invalid in the presence of
magnetic field for antiferromagnetic spin exchange interaction Yi02(SMA) . One
would naturally question the validity of SMA for spin-3 condensate since the
short-range interactions involved here are more complicated than those in
spin-1 system.

In the present paper, we study the ground state properties of a spin-3
chromium condensate subject to a uniform axial magnetic field by numerically
solving the Gross-Pitaevskii equations. We show that even though SMA is still
valid in the absence of an external magnetic field, it fails when the magnetic
field is switched on. More remarkably, we find that when the undetermined
scattering length corresponding to total spin zero channel falls into a
certain region, the magnetic field may induce a phase separation like behavior
such that the peak densities of certain spin components do not occur at the
center of the trapping potential.

This paper is organized as follows. In Sec. II, we introduce our model for
numerical calculation. The results for the ground state structure of a spin-3
condensate under an external magnetic field are presented in Sec. III.
Finally, we conclude in Sec. IV.

##  II Formulation

We consider a condensate of $N$ spin $s=3$ chromium atoms subject to a uniform
magnetic field ${\mathbf{B}}=B{\mathbf{z}}$. In mean-field treatment, the
system is described by the condensate wave functions $\psi_{m}$
($m=-3,-2,\ldots,3$). The total energy functional of the system,
$E[\psi_{m},\psi_{m}^{*}]$, can be decomposed into two parts $E=E_{0}+E_{1}$
with $E_{0}$ and $E_{1}$ being, respectively, the single-body and interaction
energies. Adopting the summation convention over repeated indices, the single-
body energy can be expressed as

$\displaystyle
E_{0}\\!=\\!\int\\!d{\mathbf{r}}\psi_{m}^{*}\left[\left(-\frac{\hbar^{2}\nabla^{2}}{2M}+V_{\mathrm{ext}}\right)\delta_{mm^{\prime}}+g\mu_{B}Bs^{z}_{mm^{\prime}}\right]\psi_{m^{\prime}},$

where $M$ is the mass of the atom, the trapping potential
$V_{\mathrm{ext}}({\mathbf{r}})=\frac{1}{2}M\omega_{\perp}^{2}(x^{2}+y^{2}+\eta^{2}z^{2})$
is assumed to be axially symmetric with $\eta$ being the trap aspect ratio,
${\mathbf{s}}=(s^{x},s^{y},s^{z})$ are the spin-3 matrices, $g=2$ is the Landé
$g$-factor of 52Cr atoms, and $\mu_{B}$ is Bohr magneton.

Figure 1: (Color online) Left panel: phase diagram of spin-3 Cr condensate in
the $a_{0}$-$B$ parameter space. The shaded region indicates the region where
phase separation occurs (see text for details). Right panel: the main
characteristics of the quantum phases.

The collisional interaction between two spin-3 atoms takes the form Ho98 ;
Ohmi98

$\displaystyle
V_{\mathrm{int}}(\mathbf{r},\mathbf{r}^{\prime})=\delta(\mathbf{r}-\mathbf{r}^{\prime})\sum_{S=0}^{2s}g_{S}\mathcal{P}_{S},$
(2)

where $\mathcal{P}_{S}$ projects onto the state with total spin $S$ and
$g_{S}=4\pi\hbar^{2}a_{S}/M$ with $a_{S=0,2,4,6}$ being the scattering lengths
for the combined symmetric channel $S$. For 52Cr, it was determined
experimentally that $a_{6}=112\,a_{B}$, $a_{4}=58\,a_{B}$, and
$a_{2}=-7\,a_{B}$ with $a_{B}$ being Bohr radius stuh , while the value of
$a_{0}$ is unknown, and we shall treat it as a free parameter in the results
presented below. Making use of the relations Ho98

$\displaystyle 1$ $\displaystyle=$ $\displaystyle\sum_{S}\mathcal{P}_{S},$
$\displaystyle{\mathbf{s}}_{1}\cdot{\mathbf{s}}_{2}$ $\displaystyle=$
$\displaystyle\sum_{S}\frac{\mathcal{P}_{S}}{2}[S(S+1)-24],$
$\displaystyle({\mathbf{s}}_{1}\cdot{\mathbf{s}}_{2})^{2}$ $\displaystyle=$
$\displaystyle\sum_{S}\frac{\mathcal{P}_{S}}{4}[S(S+1)-24]^{2},$

we may replace $\mathcal{P}_{2}$, $\mathcal{P}_{4}$, and $\mathcal{P}_{6}$ in
Eq. (2) by $1$, ${\mathbf{s}}_{1}\cdot{\mathbf{s}}_{2}$, and
$({\mathbf{s}}_{1}\cdot{\mathbf{s}}_{2})^{2}$, such that the interaction
energy functional becomes

$\displaystyle E_{1}=\frac{1}{2}\int
d{\mathbf{r}}n^{2}\left[C+\alpha|\Theta|^{2}+\beta{\rm
Tr}{\mathcal{N}}^{2}+\gamma\langle{\mathbf{s}}\rangle^{2}\right],$ (3)

where the interaction parameters are
$C=-\frac{1}{7}g_{4}+\frac{81}{77}g_{4}+\frac{1}{11}7g_{6}$,
$7\alpha=g_{0}-\frac{5}{3}g_{2}+\frac{9}{11}g_{4}-\frac{5}{33}g_{6}$,
$\beta=\frac{1}{126}g_{2}-\frac{1}{77}g_{4}+\frac{1}{198}g_{6}$, and
$\gamma=-\frac{5}{84}g_{2}+\frac{1}{154}g_{4}+\frac{7}{132}g_{6}$.
Furthermore, $n({\mathbf{r}})=\psi_{m}^{*}\psi_{m}$ is the total density,

$\Theta({\mathbf{r}})=\frac{1}{n}\sqrt{7}\langle
00|3m;3m^{\prime}\rangle\psi_{m}\psi_{m^{\prime}}$

is the singlet amplitude, and

$\langle{\mathbf{s}}\rangle({\mathbf{r}})=\frac{1}{n}\psi_{m}^{*}{\mathbf{s}}_{mm^{\prime}}\psi_{m^{\prime}}$

is the density of spin. Finally,

$\mathcal{N}_{ij}({\mathbf{r}})=\frac{1}{2n}\psi^{*}_{m}(s^{i}s^{j}+s^{j}s^{i})_{mm^{\prime}}\psi_{m^{\prime}},\quad
i,j=x,y,z$

is the nematic tensor, and to obtain it, we have utilized the relation

$\langle({\mathbf{s}}_{1}\cdot{\mathbf{s}}_{2})^{2}\rangle={\rm Tr}{\cal
N}^{2}-\frac{1}{2}\langle{\mathbf{s}}_{1}\rangle\cdot\langle{\mathbf{s}}_{2}\rangle.$

The nematic tensor was first introduced in the liquid crystal physics as the
order parameter $\mathcal{N}$ de Gennes  to describe the orientation order of
the liquid crystal molecules. Since $\mathcal{N}$ is Hermitian, it can be
diagonalized with all eigenvalues $\lambda_{a=1,2,3}$ (ordered as
$\lambda_{1}\leq\lambda_{2}\leq\lambda_{3}$) being real and the corresponding
principle axes $\hat{\mathbf{e}}_{a}$ being mutually orthogonal. Unless all
three eigenvalues are equal, the systems with two identical eigenvalues are
usually refer to as uniaxial nematics, while those with three unequal
eigenvalues are biaxial ones. More importantly, $\lambda_{a}$ can be
determined by performing Stern-Gerlach experiments along
$\hat{\mathbf{e}}_{a}$ Ho06 . As it can be seen from Eq. (3), different
quantum phases originate from the competition of $\Theta$,
$\langle\mathbf{s}\rangle$, and $\mathcal{N}$. Following the discussion of
Diener and Ho Ho06 , we shall characterize phases in a spin-3 Cr condensate
using the condensate wave functions $\psi_{m}$, singlet amplitude $\Theta$,
spin $\langle{\mathbf{s}}\rangle$, and nematic tensor $\mathcal{N}$.

Figure 2: (Color online) The typical $\rho$ dependence of the densities for
all spin components in the phase separation region. From (a) to (d), the
magnetic field strengths (in units of mG) are, respectively, $B=0.0211$,
$0.0633$, $0.0844$, and $0.1689$. The scattering length $a_{0}=5.47a_{B}$ is
the same for all figures. The densities of those components not shown in the
figures are too small to be seen.

To simplify the numerical calculations, we shall focus on highly oblate trap
geometries ($\eta\gg 1$) such that the condensate can be regarded as quasi-
two-dimensional whose motion along the $z$-axis is frozen to the ground state
of the axial harmonic oscillator. The condensate wave functions can then be
decomposed into

$\displaystyle\psi_{m}({\mathbf{r}})=(\eta/\pi)^{1/4}e^{-\eta
z^{2}/2}\phi_{m}({\bm{\rho}})$ (4)

with ${\bm{\rho}}=(x,y)$ and $\phi_{m}$ being normalized to the total number
of atoms $N$, i.e., $\int d{\mathbf{r}}\phi_{m}^{*}\phi_{m}=N$. After
integrating out the $z$ variable, $E_{0}$ gives an extra constant, while the
interaction parameters $C$, $\alpha$, $\beta$, and $\gamma$ are all rescaled
by a factor $(\eta/2\pi)^{1/2}$. The mean-field wave functions
$\\{\psi_{m}\\}$ are obtained by minimizing the total energy functional
numerically using imaginary time evolution. We shall focus our study on the Cr
line Ho06 , namely only the scattering length $a_{0}$ is allowed to changed
freely, since experimentally, it is the most relevant case. For all results
presented in the present work, we have chosen $N=10^{5}$,
$\omega_{\perp}=2\pi\times 100\,\mathrm{Hz}$, and $\eta=10$. Correspondingly,
the dimensionless length unit $a_{\perp}=\sqrt{\hbar/(M\omega_{\perp})}$ is
adopted in throughout this paper.

We remark that we have neglected the magnetic dipole-dipole interaction energy
in Eq. (3) for simplicity, as in the present work, we are concentrating on
investigating how short-range interaction and magnetic field affect the ground
state wave function. The ignorance of dipolar interaction in spinor Cr
condensate was also justified in Ref. Ho06 . Moreover, we have numerically
confirmed that for the parameter used in this paper, the dipole-dipole
interaction energy is much smaller than short-ranged spin-dependent
interaction energy when the condensate is not polarized by the magnetic field.

##  III Results

Figure 1 summarizes the main results of this paper. In the left panel of Fig.
1, we present the phase diagram of spin-3 Cr condensate in the $a_{0}$-$B$
parameter space, here we have adopted the similar notations for different
phases as in Ref. Ho06 . In the right panel, we tabulate the major characters
of each phase. We remark that the resolution of phase diagram is limited by
step sizes of $a_{0}$ and $B$ when we numerically scan the parameter plane,
therefore, it is possible that more details may emerge by reducing the step
sizes.

###  III.1 Condensate wave functions

The numerical results indicate that the condensate wave functions can always
be expressed as

$\displaystyle\phi_{m}({\bm{\rho}})=\sqrt{n_{m}({\rho})}e^{i\vartheta_{m}},$
(5)

where the density of $m$th component $n_{m}({\rho})$ is an axially symmetric
function and the corresponding phase $\vartheta_{m}$ is a constant independent
of the spatial coordinates. In case the external magnetic field is completely
switched off, we find that all wave functions $\phi_{m}({\mathbf{r}})$ have
the same density profile, indicating that the SMA is valid for spin-3
condensates in the absence of magnetic field. We note that this conclusion
also holds true for spin-$1$ and -$2$ condensates.

Once the external magnetic field is applied, SMA quickly becomes invalid. More
remarkably, as shown in Fig. 2, when control parameters $a_{0}$ and $B$ fall
into the shaded region in the left panel of Fig. 1, the peak densities of at
least one of the spin components among $m=-3$, $\pm 2$, and $0$ do not occur
at the center of the trap, in analogy to the phase separation in a two-
component condensate binexp ; binary . In the absence of magnetic field, the
system is symmetric under SO(3) rotation of the spin, and $m=-3$ component can
be populated. However, immediately after we switch on the magnetic field, this
SO(3) symmetry is broken such that $m=\pm 1$ spin components are highly
populated under a very weak magnetic field. As one continuously increases the
magnetic field, the occupation number in $m=-3$ component increases with
density in the margin of the trap growing faster than that in the center,
which induces the phase separation like behavior. When the population in
$m=-3$ component dominates, the peak densities of all spin component occur at
the center of the trap. We remark that similar behavior of the wave functions
also appears outside the Cr line Ho06 .

Figure 3: (color online) The instable region (enclosed by solid line) of a
homogeneous Cr condensate and the phase separation region (enclosed by dashed
line) of a trapped Cr condensate (Same as that in Fig. 1).

To gain more insight into the origin of the phase separation like behavior, we
consider a homogeneous Cr condensate where each spin component has already
condensed into the zero momentum mode. The wave function
$\psi_{m}({\mathbf{r}})$ for phase unseparated state is then replaced by a
uniform $c$-number

$\displaystyle\bar{\psi}_{m}=\sqrt{n}\xi_{m},$ (6)

where $n$ is a real constant and $\xi_{m}$ are complex constants. The ground
state can be obtained by minimizing the total energy $E$ subject to the
normalization condition $\xi_{m}^{*}\xi_{m}=1$. In such a way, we have
reproduce the phase diagram in Ref. Ho06 . To confirm that those phases are
indeed the ground states, we introduce a new set of variables, $\zeta_{p}$ and
$\zeta_{p+1}$, corresponding to, respectively, the real and imaginary parts of
the wave function $\xi_{m}$ as

$\displaystyle\zeta_{p=2(3-m)+1}={\rm Re}[\xi_{m}]\mbox{ and
}\zeta_{p=2(3-m)+2}={\rm Im}[\xi_{m}].$

We then construct the Hessian matrix
${\bm{H}}=\left[\frac{\partial^{2}E}{\partial\zeta_{p}\partial\zeta_{q}}\right]$.
For a solution to be stable, the Hessian matrix must be positive definite
timmer . In Fig. 3, we present the unstable region of a homogeneous Cr
condensate on $a_{0}$-$B$ plane. To obtain it, we have chosen the density to
be $n=3.3\times 10^{14}\,{\rm cm}^{-3}$ which is the peak density of the
trapped system in our numerical calculations. One immediately sees that the
unstable region of a homogeneous condensate roughly agrees with the phase
separation region of the trapped system, which suggests that the possible
origin of the phase separation behavior is the instability of the phase
unseparated solution.

We emphasize that, unlike in a binary Bose-Einstein condensate where the
emergence of phase separation is determined by the strengths of intra- and
inter-species interactions, here for a given scattering length $a_{0}$, the
phase separation like behavior is induced by the magnetic field.

###  III.2 Singlet amplitude

Since the spatial independence of $\Theta({\mathbf{\rho}})$ is a necessary
condition for SMA, it can also be used as a criterion to check the validity of
SMA. As shown in Fig. 4, $|\Theta|$ is a constant when $B=0$; while
immediately after the magnetic field is turned on, $|\Theta|$ becomes
spatially dependent. In addition, the peak value of $|\Theta|$ decreases
continuously as one increases the magnetic field until it completely vanish.

In Fig. 4 (a), $|\Theta(\rho)|$ becomes zero only after the condensate is
completely polarized, while in (b) and (c), it vanishes once the system enters
the ${\rm H}_{1}$ phase. Therefore, using singlet amplitude, we may map out
the phase boundaries between ${\rm A}_{1}$ and ${\rm FF}$, ${\rm Z}$ and ${\rm
H}_{1}$, and ${\rm B}_{1}$ and ${\rm H}_{1}$. However, $\Theta$ alone is
incapable of determining other phase boundaries. Finally, we note that, for
$a_{0}>8.9a_{B}$, the value of $|\Theta|$ drops much faster with the
increasing magnetic field than that corresponding to $a_{0}<8.9a_{B}$, as
shown below this behavior has a direct impact on the magnetization curve of
the system.

Figure 4: (Color online) The typical behaviors of $|\Theta(\rho)|$ for
$a_{0}=-8.27a_{B}$ (a), $5.47a_{B}$ (b), and $12.35a_{B}$ (c). In descending
order of central value, the lines in (a) correspond to the magnetic field (in
units of mG) $B=0$, $0.0244$, $0.1689$, $0.2533$, and $0.3377$; those in (b)
correspond to $B=0$, $0.0422$, $0.0844$, $0.1266$, and $0.19$; and finally,
those in (c) correspond to $B=0$, $0.0211$, $0.0422$, and $0.0633$. Figure 5:
(Color online) The field dependence of the magnetization for
$a_{0}=-59.82a_{B}$ (solid line), $-25.45a_{B}$ (dashed line), $5.47a_{B}$
(dash-dotted line), and $12.35a_{B}$ (dotted line). For $a_{0}>8.9a_{B}$
($\alpha>0$), the $\mathcal{M}(p)$ curves corresponding to different $a_{0}$’s
are indistinguishable.

###  III.3 Magnetization

We now turn to study magnetic field dependence of the total magnetization. To
this end, we define the reduced magnetization as

$\displaystyle\mathcal{M}=N^{-1}\int d{\mathbf{\rho}}\langle s^{z}\rangle.$
(7)

Unlike in Ref. Makela07  where the total magnetization is conserved, here we
allow it to change freely. Therefore, the transverse components of the spin,
$\langle s^{x}\rangle$ and $\langle s^{y}\rangle$, are always zero. Figure 5
shows the field dependence of the reduced magnetization, which approaches $-3$
when $B$ reaches the saturation field. We note that, for $a_{0}<8.9a_{B}$, the
behavior of $\mathcal{M}(B)$ slightly depends on the value of $a_{0}$; while
for $a_{0}>8.9a_{B}$, the magnetization curves corresponding to different
$a_{0}$’s become indistinguishable. Consequently, as shown in Fig. 1, the
saturation field for the former case is a decreasing function of $a_{0}$,
while for the latter one, it becomes a constant. The $a_{0}$ independence of
the magnetization for $a_{0}>8.9a_{B}$ case can be qualitatively understood as
follows. The scattering length $a_{0}$ only contributes to the total energy
through singlet amplitude $\Theta$. As shown in Fig. 4, for $a_{0}>8.9a_{B}$,
$\Theta$ vanishes quickly as one increases the magnetic field, such that
varying $a_{0}$ only yields a negligible effect on magnetization curve. With
the help magnetization, we can further identify the phase boundary between
${\rm H_{1}}$ and ${\rm FF}$ phases.

Figure 6: (Color online) The spatial dependence of $\lambda_{1}$ (dash-dotted
lines), $\lambda_{2}$ (dashed lines), and $\lambda_{3}$ (solid lines) for
$a_{0}=5.47a_{B}$ (left panels) and $12.35a_{B}$ (right panels). The magnetic
field strength (in units of mG) is denoted in each figure.

###  III.4 Nematic tensor

To determine other phase boundaries, we have to rely on the nematic tensor. In
Fig. 6, we plot typical behavior of the eigenvalues of nematic tensor under
different $a_{0}$ and magnetic fields. As a consequence of the failure of SMA,
$\lambda_{a}$’s are generally spatially dependent. However, some of their
characteristics obtained under SMA remain to be true.

The full ferromagnet (FF) phase occurs when the magnetic field exceeds the
saturation field such that only $m=-3$ component is occupied. The nematic
tensor takes a diagonal form with $\lambda_{1}=\lambda_{2}=\frac{3}{2}$ and
$\lambda_{3}=9$. For the wave functions of A1 and H1 phases, only two spin
states are populated: other than a common $m=-3$ state, $m=3$ and $2$ are also
occupied for, respectively, A1 and H1 phases. One can easily deduce that the
nematic tensors of phases A1 and H1 are, respectively, ${\rm
diag}\\{\frac{3}{2},\frac{3}{2},9\\}$ and $n^{-1}{\rm
diag}\\{\frac{3}{2}n_{-3}+4n_{2},\frac{3}{2}n_{-3}+4n_{2},9n_{-3}+4n_{2}\\}$.
Since for both cases, ${\cal N}_{zz}$ is the largest eigenvalue, we have
$\hat{\mathbf{e}}_{3}\parallel\hat{\mathbf{z}}$. Moreover,
$\hat{\mathbf{e}}_{1}$ and $\hat{\mathbf{e}}_{2}$ are spatially independent.

For G1 phase, $m=\pm 2$ and $0$ states are unoccupied, consequently, ${\cal
N}$ becomes a block diagonal matrix with one of the eigenvalues being ${\cal
N}_{zz}=n^{-1}\left[9(n_{3}+n_{-3})+n_{1}+n_{-1}\right]$. Furthermore, from
numerical results, we find that ${\cal N}_{zz}$ is always the smaller
eigenvalue and $\lambda_{2}({\bm{\rho}})\neq\lambda_{3}({\bm{\rho}})$, which
suggests that G1 is a biaxial nematic phase with
$\hat{\mathbf{e}}_{1}\parallel\hat{\mathbf{z}}$.

All spin components of ${\rm B}_{1}$ and ${\rm Z}$ phases are populated, they
are all are biaxial nematic with three unequal and spatially dependent
$\lambda$’s. The principal axes for these phases are also spatially
dependents. The only difference is that for ${\rm B}_{1}$ phase we can
identify that either ${\mathbf{e}}_{1}$ or ${\mathbf{e}}_{2}$ is perpendicular
to $z$-axis.

##  IV Conclusions

To conclude, we have mapped out the phase diagram of a spin-3 Cr condensate
subject to an external magnetic field based on the numerical calculation of
the ground state wave function. In particular, we show that SMA becomes
invalid for Cr condensates under a finite magnetic field. More remarkably, if
the unknown scattering length $a_{0}$ falls into the region
$[-0.37,8.2]a_{B}$, a phase separation like behavior may be induced by the
magnetic field. We also point out that such behavior might originate from the
instability of a phase unseparated solution. As a future work, we shall
investigate the ground state structure of a spin-3 Cr condensate by including
the magnetic dipole-dipole interaction.

###### Acknowledgements.

We thank Han Pu for useful discussion. This work is supported by NSFC (Grant
No. 10674141), National 973 program (Grant No. 2006CB921205), and the “Bairen”
program of the Chinese Academy of Sciences.

## References

  * (1) A. Griesmaier, J. Werner, S. Hensler, J. Stuhler, and T. Pfau, Phys. Rev. Lett. 94, 160401 (2005).
  * (2) J. Stuhler, A. Griesmaier, T. Koch, M. Fattori, T. Pfau, S. Giovanazzi, P. Pedri, and L. Santos, Phys. Rev. Lett. 95, 150406 (2005).
  * (3) T. Lahaye, J. Metz, B. Fröhlich, T. Koch, M. Meister, A. Griesmaier, T. Pfau, H. Saito, Y. Kawaguchi and M. Ueda, Phys. Rev. Lett. 101, 080401 (2008).
  * (4) J. Stenger, S. Inouye, D. M. Stamper-Kurn, H.-J. Miesner, A. P. Chikkatur, and W. Ketterle, Nature (London) 396, 345 (1998)
  * (5) M. Barrett, J. Sauer, and M. S. Chapman, Phys. Rev. Lett. 87, 010404 (2001).
  * (6) T.-L. Ho, Phys. Rev. Lett. 81, 742 (1998).
  * (7) T. Ohmi and K. Machida, J. Phys. Soc. Jpn. 67, 1822 (1998).
  * (8) C. K. Law, H. Pu, and N. P. Bigelow, Phys. Rev. Lett. 81, 5257 (1998).
  * (9) M. Koashi and M. Ueda, Phys. Rev. Lett. 84, 1066 (2000).
  * (10) C. V. Ciobanu, S.-K. Yip, and T.-L. Ho, Phys. Rev. A, 61, 033607 (2000).
  * (11) H. Schmaljohann, M. Erhard, J. Kronjäger, M. Kottke, S. van Staa, L. Cacciapuoti, J. J. Arlt, K. Bongs, and K. Sengstock, Phys. Rev. Lett. 92, 040402 (2004).
  * (12) M.-S. Chang, C. D. Hamley, M. D. Barrett, J. A. Sauer, K. M. Fortier, W. Zhang, L. You, and M. S. Chapman, Phys. Rev. Lett. 92, 140403 (2004).
  * (13) T. Kuwamoto, K. Araki, T. Eno, and T. Hirano, Phys. Rev. A 69, 063604 (2004).
  * (14) R. B. Diener and T.-L. Ho, Phys. Rev. Lett. 96, 190405 (2006).
  * (15) L. Santos and T. Pfau, Phys. Rev. Lett. 96, 190404 (2006).
  * (16) H. Mäkelä and K.-A. Suominen, Phys. Rev. A. 75, 033610 (2007).
  * (17) R. Barnett, A. Turner, and E. Demler, Phys. Rev. Lett. 97, 180412 (2006); ibid. Phys. Rev. A 76, 013605 (2007).
  * (18) S.-K. Yip, Phys. Rev. A 75, 023625 (2007).
  * (19) J.-S. Bernier, K. Sengupta, and Y.-B. Kim, Phys. Rev. B 76, 014502 (2007).
  * (20) Y. Kawaguchi, H. Saito, and M. Ueda, Phys. Rev. Lett. 96, 080405 (2006).
  * (21) S. Yi, Ö. E. Müstecaplıoğlu, C. P. Sun, and L. You, Phys. Rev. A 66, 011601(R) (2002);
  * (22) P. G. de Gennes and J. Prost, _The Physics of Liquid Crystals_ , 2nd ed (Oxford University Press, London, 1993).
  * (23) C. J. Myatt, E. A. Burt, R. W. Ghrist, E. A. Cornell, and C. E. Wieman, Phys. Rev. Lett. 78, 586 (1997); D. S. Hall, M. R. Matthews, J. R. Ensher, C. E. Wieman, and E. A. Cornell, Phys. Rev. Lett. 81, 1539 (1998).
  * (24) T. L. Ho and V. B. Shenoy, Phys. Rev. Lett. 77, 3276 (1996); H. Pu and N. P. Bigelow, Phys. Rev. Lett. 80, 1130 (1998).
  * (25) E. Timmermans, Phys. Rev. Lett. 81, 5718 (1998)