%% SPDX-License-Identifier: CC0-1.0
%%
%% Copyright (C) 2025 Woj. Kosior <koszko@koszko.org>
\documentclass[a4paper,12pt,twoside,notitlepage]{report}
\usepackage{rotating}
\usepackage[
margin=2.5cm,
marginparwidth=1.5cm,
marginparsep=2mm,
foot=1cm,
head=1cm
]{geometry}
\renewcommand{\baselinestretch}{1.5}
\newcommand{\smallStretchValue}{1.2}
\newenvironment{smallStretch}{\setstretch{\smallStretchValue}}{}
\usepackage{titlesec}
\titleformat
{\chapter} % command
[hang] % shape
{\bfseries\Large} % format
{\thechapter{}.{ }} % label
{0pt} % sep
{} % before-code
[] % after-code
\usepackage{fancyhdr}
\usepackage[T1]{fontenc}
\usepackage{xurl}
\usepackage[style=alphabetic,backend=biber,urldate=long,maxbibnames=9]{biblatex}
\usepackage[polish,english]{babel}
\DefineBibliographyStrings{english}{%
mathesis = {Master's thesis},
}
\addbibresource{doc.bib}
\renewcommand*\finalnamedelim{, \addspace{}and\addspace{}}
\usepackage{mathptmx}
\usepackage{fontspec}
\usepackage{newunicodechar}
\newfontfamily{\fallbackfont}{DejaVu Sans}[Scale=MatchLowercase]
\DeclareTextFontCommand{\textfallback}{\fallbackfont}
\newunicodechar{│}{\textfallback{│}}
\newunicodechar{├}{\textfallback{├}}
\newunicodechar{─}{\textfallback{─}}
\newunicodechar{˷}{,,}
\usepackage{footnote}
\usepackage{caption}
\usepackage{setspace}
\captionsetup[lstlisting]{
font={stretch=\smallStretchValue}
} % fix to prevent listings' changed stretch from affecting their captions
\usepackage[table]{xcolor}
\usepackage{array}
\usepackage{calc}
% https://tex.stackexchange.com/questions/249040/scale-column-of-a-table-in-percentage-of-textwidth#answer-249043
\newdimen\netTableWidth
\newcommand{\columnsCount}[1]{%
\netTableWidth=\dimexpr
\linewidth
- #1\tabcolsep - #1\tabcolsep
- #1\arrayrulewidth -2\arrayrulewidth
\relax%
}
\newenvironment{fancycell}
{%
\hspace{0.1in}%
\nolinebreak%
\begin{minipage}[t]{\dimexpr\linewidth-0.1in\relax}
\raggedright
\hspace{-0.15in}%
}
{%
\end{minipage}%
\vspace{0.07in}
}
\usepackage{tikz}
\newcommand{\lightbullet}{%
\begin{tikzpicture}
\pgfmathsetlengthmacro\Xheight{height("X")}
\draw (0, 0) node[
inner sep=0,
anchor=east,
minimum height=\Xheight
] {};
\fill[radius=0.25*\Xheight] circle;
\end{tikzpicture}%
}
\def\cellitems{\def\item{\par
\noindent\hbox to1.2em{\hss\lightbullet\hss\hss\hss}\hangindent=1.5em }}
\usepackage[hyperfootnotes=false,pdftex]{hyperref}
\hypersetup{
colorlinks = true,
linkbordercolor = .,
linkcolor = [rgb]{0,0.2,0}, % to be changed after ToC&friends
urlcolor = [rgb]{0,0,0.5},
citecolor = [rgb]{0.5,0,0}
}
\definecolor{PATCHGREEN}{rgb}{0,0.5,0}
\definecolor{PATCHRED}{rgb}{0.5,0,0}
\definecolor{TEXTGRAY}{gray}{0.2}
\definecolor{FRAMEGRAY}{gray}{0.6}
\usepackage{listings}
\usepackage{accsupp}
\renewcommand{\lstlistlistingname}{List of Listings}
\lstset{
basicstyle=\fontsize{7}{9}\selectfont\ttfamily,
% lineskip=-0.2em,
numbers=left,
numberstyle=\fontsize{7}{9}\color{TEXTGRAY},
inputencoding=utf8,
escapeinside={(*}{*)},
extendedchars=true,
breaklines=true,
postbreak=\mbox{%
\hspace{-5em}%
{\BeginAccSupp{ActualText={}}%
\textcolor{TEXTGRAY}{$\hookrightarrow$}%
\space%
\EndAccSupp{}%
}
},
breakautoindent=false,
captionpos=b,
frame=tbrl,
rulecolor=\color{FRAMEGRAY}
}
\lstdefinelanguage{diffoscope}{
delim = [s][\bfseries]{@@}{@@},
moredelim = [l][\color{PATCHRED}]{\ -},
moredelim = [l][\color{PATCHGREEN}]{\ +}
}
\lstdefinelanguage{shc-patch}{
delim = [s][\bfseries]{@@}{@@},
moredelim = [l][\color{PATCHRED}]{-shell},
moredelim = [l][\color{PATCHRED}\bfseries]{---},
moredelim = [l][\color{PATCHGREEN}]{+shell},
moredelim = [l][\color{PATCHGREEN}\bfseries]{+++}
}
\definecolor{tango-string}{HTML}{5c3566}
\definecolor{tango-comment}{HTML}{5f615c}
\definecolor{tango-keyword}{HTML}{346604}
\lstdefinelanguage{guix-package-definition}[]{Lisp}{
stringstyle = \color{tango-string},
commentstyle = \itshape\color{tango-comment},
keywordsprefix = {\#:},
keywords = {},
keywordstyle = \color{tango-string},
keywords = [2]{list,lambda,for-each,define-public},
keywordstyle = [2]\color{tango-keyword},
keywords = [3]{\#t},
keywordstyle = [3]\bfseries
}
\lstdefinelanguage{guix-commit}[]{guix-package-definition}{
delim = [s][\bfseries]{@@}{@@},
moredelim = [l][\color{PATCHRED}]{-\ },
moredelim = [l][\color{PATCHGREEN}]{+\ }
}
\lstdefinelanguage{shell-command}{
delim = [s][\color{tango-keyword}]{--}{\ },
alsoletter = {\\},
keywords = {\\},
keywordstyle = \color{tango-string}
}
\lstdefinelanguage{package-lock-json}{
stringstyle = \color{tango-string},
string = [b]{"}
}
\newcommand{\code}[1]{\mbox{\color{TEXTGRAY}\fontsize{8}{10}\texttt{#1}}}
%% https://tex.stackexchange.com/questions/320342/lstinputlisting-ranges-and-unicode-characters
\makeatletter
\lst@InputCatcodes
\def\lst@DefEC{%
\lst@CCECUse \lst@ProcessLetter
^^80^^81^^82^^83^^84^^85^^86^^87^^88^^89^^8a^^8b^^8c^^8d^^8e^^8f%
^^90^^91^^92^^93^^94^^95^^96^^97^^98^^99^^9a^^9b^^9c^^9d^^9e^^9f%
^^a0^^a1^^a2^^a3^^a4^^a5^^a6^^a7^^a8^^a9^^aa^^ab^^ac^^ad^^ae^^af%
^^b0^^b1^^b2^^b3^^b4^^b5^^b6^^b7^^b8^^b9^^ba^^bb^^bc^^bd^^be^^bf%
^^c0^^c1^^c2^^c3^^c4^^c5^^c6^^c7^^c8^^c9^^ca^^cb^^cc^^cd^^ce^^cf%
^^d0^^d1^^d2^^d3^^d4^^d5^^d6^^d7^^d8^^d9^^da^^db^^dc^^dd^^de^^df%
^^e0^^e1^^e2^^e3^^e4^^e5^^e6^^e7^^e8^^e9^^ea^^eb^^ec^^ed^^ee^^ef%
^^f0^^f1^^f2^^f3^^f4^^f5^^f6^^f7^^f8^^f9^^fa^^fb^^fc^^fd^^fe^^ff%
^^^^2502^^^^251c^^^^2500% `│', `├' and `─'
^^00}
\lst@RestoreCatcodes
\makeatother
%% was useful when I had no chapters and current chapters were sections
% \usepackage[section]{placeins}
% https://aty.sdsu.edu/bibliog/latex/floats.html
% Alter some LaTeX defaults for better treatment of figures:
% See p.105 of "TeX Unbound" for suggested values.
% See pp. 199-200 of Lamport's "LaTeX" book for details.
% General parameters, for ALL pages:
\renewcommand{\topfraction}{0.9} % max fraction of floats at top
\renewcommand{\bottomfraction}{0.8} % max fraction of floats at bottom
% Parameters for TEXT pages (not float pages):
\setcounter{topnumber}{2}
\setcounter{bottomnumber}{2}
\setcounter{totalnumber}{4} % 2 may work better
\setcounter{dbltopnumber}{2} % for 2-column pages
\renewcommand{\dbltopfraction}{0.9} % fit big float above 2-col. text
\renewcommand{\textfraction}{0.07} % allow minimal text w. figs
% Parameters for FLOAT pages (not text pages):
\renewcommand{\floatpagefraction}{0.7} % require fuller float pages
% N.B.: floatpagefraction MUST be less than topfraction !!
\renewcommand{\dblfloatpagefraction}{0.7} % require fuller float pages
%% \usepackage{float}
%% \newfloat{flist}{H}{dummyfile}
%% \newenvironment{fitemize}
%% {\begin{itemize}}
%% {\end{itemize}}
%% %% {\begin{flist}\begin{itemize}}
%% %% {\end{itemize}\vspace{-2.5em}\end{flist}}
%% \newenvironment{fenumerate}
%% {\begin{enumerate}}
%% {\end{enumerate}}
%% %% {\begin{flist}\begin{enumerate}}
%% %% {\end{enumerate}\vspace{-2.5em}\end{flist}}
\usepackage{enumitem}
\usepackage{svg}
\usepackage{graphics}
%% \newcommand{\workNote}[1]{\emph{\color{red}\footnotesize(#1)}}
%% \newcommand{\TODONote}[1]{\emph{\color{red}\footnotesize(TODO: #1)}}
%% \newcommand{\marginNote}[2][9in]{%
%% \marginpar{%
%% \setstretch{1.1}%
%% \begin{turn}{90}%
%% \begin{minipage}{#1}%
%% \workNote{#2}%
%% \end{minipage}%
%% \end{turn}%
%% }%
%% }
\newcommand{\givemeatilde}{%
{\raisebox{0.5ex}{\texttildelow}}%
}
\newcommand{\tresholdDate}{April 14th, 2025}
\newcommand{\tresholdGuixCommit}{\code{143faecec3}}
\newcommand{\tresholdDateAndCommit}
{\tresholdDate{}, GNU Guix Git commit \tresholdGuixCommit{}}
\newcommand{\debianTresholdDate}{June 3rd, 2025}
\input{definitions-computed-from-results.tex}
\fancypagestyle{fancyplain}{ %
\fancyfoot[C]{Kraków, 2025}
\renewcommand{\headrulewidth}{0pt} % remove lines as well
\renewcommand{\footrulewidth}{0pt}
}
\title{Software Provenance Assurance through Reproducible Builds}
% https://tex.stackexchange.com/questions/15804/how-to-use-the-content-of-title-as-a-reference
\makeatletter
\let\inserttitle\@title
\makeatother
\newcommand{\insertauthor}{Wojciech Kosior}
\hypersetup{
pdftitle = {\inserttitle},
pdfauthor = {\insertauthor}
}
\begin{document}
\newpage
\pagenumbering{roman}
\titlepage
\thispagestyle{fancyplain}
\fancyhf{}
\fancyfoot[C]{Kraków, 2025}
\mbox{}
\vspace{0.5in}
\begin{smallStretch}
\fontfamily{cmr}\selectfont
\sffamily
\begin{center}
\large
\includesvg[
width=0.2\linewidth,
inkscapelatex=false
]{agh.svg}
\vspace{0.2in}
\MakeUppercase{\small\bfseries {\large{}AGH} {\large{}U}niversity of
{\large{}K}rakow}
\vspace{0.2in}
\MakeUppercase{\small\bfseries THE FACULTY OF COMPUTER SCIENCE,
\\ ELECTRONICS AND TELECOMMUNICATIONS}
\vspace{0.45in}
Master's thesis
\vspace{0.45in}
\textit{\inserttitle}
\vspace{0.2in}
\textit{\normalsize{}Potwierdzanie autentyczności oprogramowania \\ poprzez
powtarzalność kompilacji}
\vspace{0.45in}
Keywords: software supply chain threats, reproducible builds, software
provenance, software packaging, npm Registry
\end{center}
\vspace*{\fill}
\renewcommand{\arraystretch}{\baselinestretch}
\columnsCount{2}
\begin{tabular}{ m{.35\netTableWidth} m{.65\netTableWidth} }
Author: & \insertauthor \\
Major: & Cybersecurity \\
Supervisor: & dr hab.\ inż.\ Piotr Pacyna, prof.\ AGH
\end{tabular}
\end{smallStretch}
\clearpage
\chapter*{Acknowledgements}
I could have decided not to enroll for the MSc course in the first place. But,
having experienced some failures in my career, I started asking what God would
like me to do. I recalled that even though at various moments it was unpleasant
to be a student, university was a place that suited me more that places I have
been to afterwards. I assumed that maybe -- just maybe -- God did not want me
to succeed anywhere else because He wants me to be happy here, in the academia.
And so I am, finishing this unusual piece of research. Thank God.
I also want to thank my wife, Joanna, who supported me even though she regularly
had to suffer listening about my boring computer topics. I thank my father, who
at times seems to care for my successful defence even more than I do.
Finally, I could not forget about my supervisor who -- luckily for me -- was
corageous enough to undertake supervising a thesis in the software supply chain
field, which few students pursued before. Thank you!
\begin{smallStretch}
\clearpage
\setcounter{tocdepth}{1}
\tableofcontents
\clearpage
\phantomsection{}
\addcontentsline{toc}{chapter}{\listfigurename}
\listoffigures
\clearpage
\phantomsection{}
\addcontentsline{toc}{chapter}{\lstlistlistingname}
\lstlistoflistings
\clearpage
\phantomsection{}
\addcontentsline{toc}{chapter}{\listtablename}
\listoftables
\end{smallStretch}
\clearpage
\phantomsection{}
\addcontentsline{toc}{chapter}{\abstractname}
\begin{abstract}
Software faces risk of contamination on multiple stages of its creation and
distribution. One such stage is software's build, where its initial form --
the source code -- is transformed into a form suitable for distribution. A
build is called reproducible when it yields bit-to-bit identical outputs when
repeated. The reproducible build can be secured by repeating it on multiple
infrastructures and comparing the outputs. This decreaces the risk of the
software getting contaminated through the build infrastructure used. Certain
software projects -- in particular, the Debian operating system -- already
levarage reproducible builds as a security tool. Meanwhile, several software
ecosystems rely on repositories whose packages cannot be reliably rebuilt and
tested for reproducibility. An example is a popular repository called npm
Registry. The software available through the npm Registry gets included in
reproducibility-focused distributions like Debian at slow pace. A great
number and complexity of dependency relations between npm packages were
hypothesized to be the primary hindrances to this process. In this work, a
statistical analysis of the npm ecosystem was performed and existing
approaches to reproducibility in the context of dependency resolution were
identified. Additionally, alternative approaches were proposed that would
allow for easier packaging of npm software while making reproducibility
achievable. To verify several stated hypotheses, an experiment was performed,
where builds of the most popular npm projects were attempted. Projects were
built multiple times to test what subset of their npm Registry dependencies
can be removed without causing the build to fail. The complexity and size of
project's minimal dependency tree was found not to be related to the
likelihood of the project having a corresponding Debian package. The results
lead to conclusion that even numerous and complex dependency relations can be
handled in existing reproducibility-focused software distributions. This
means that employing the proposed new approaches is not necessary to apply
reproducibility to npm software in the future. It also means that the
inclusion of npm software in reproducibility-focused software distributions is
mostly hindered by other factors that need to be countered. These were also
pointed at the end of this work.
\end{abstract}
\clearpage
\selectlanguage{polish} \phantomsection{}
\addcontentsline{toc}{chapter}{\abstractname}
\begin{abstract}
Bezpieczeństwo oprogramowania może zostać zagrożone na różnych etapach jego
tworzenia i~dystrybucji. Jednym z~nich jest szeroko rozumiana kompilacja
oprogramowania, gdzie jego pierwotna postać -- kod źródłowy -- jest
przekształcana do postaci odpowiedniej dla dystrybucji. Proces kompilacji
nazywamy powtarzalnym, jeśli przy wielokrotnym przeprowadzeniu daje wyniki bit
do bitu identyczne. Powtarzalny proces kompilacji może zostać zabezpieczony
poprzez przeprowadzenie go na różnych infrastrukturach i~porównanie wyników.
Zmniejsza to ryzyko zanieczyszczenia kodu oprogramowania przez użytą
infrastrukturę. Pewne oprogramowanie -- w~szczególności system Debian -- już
wykorzystuje powtarzalność jako narzędzie bezpieczeństwa. Jednocześnie,
niektóre ekosystemy oprogramowania polegają na repozytoriach, których pakiety
nie mogą być w~sposób niezawodny przekompilowane i~sprawdzone pod kątem
powtarzalności. Przykładem jest popularne repozytorium o~nazwie npm Registry.
Oprogramowanie dostępne przez~npm Registry jest też, aczkolwiek w~wolnym
tempie, włączane do dystrybucji typu Debian dbających o~powtarzalność
kompilacji. Według postawionej hipotezy to duża liczba i~złożoność relacji
zależności między pakietami npm są głównymi utrudnieniami w~tym procesie.
W~ramach pracy została wykonana analiza statystyczna ekosystemu npm oraz
zostały zidentyfikowane istniejące podejścia do powtarzalności w~kontekście
procesu rozwiązywania zależności. Dodatkowo, zostały zaproponowane
alternatywne podejścia, w~których pakowanie oprogramowania npm miałoby być
łatwiejsze, a~powtarzalność byłaby wciąż osiągalna. Dla zweryfikowania
postawionych hipotez przeprowadzony został eksperyment -- próba kompilacji
najpopularniejszych projektów npm. Projekty kompilowano wielokrotnie,
sprawdzając, jaka część ich zależności z~npm Registry może zostać usunięta
z~zachowaniem powodzenia procesu kompilacji. Złożoność i~rozmiar minimalnego
drzewa zależności projektu okazały się nie być powiązane
z~prawdopodobieństwiem istnienia odpowiadającego pakietu w~Debianie. Wyniki
prowadzą do wniosku, że istniejące dystrubucje oprogramowania dbające
o~powtarzalność mogą sobie poradzić także z~licznymi i~złożonymi relacjami
zależności. Oznacza to, że wprowadzenie zaproponowanych nowych podejść nie
jest konieczne, żeby można było w~przyszłości zastosować powtarzalność do
oprogramowania npm. Oznacza to też, że włączanie oprogramowania npm do
dystrybucji oprogramowania dbających o~powtarzalność jest w~głównej mierze
powstrzymywane przez inne czynniki wymagające zwalczenia. Zostały one
wskazane pod koniec pracy.
\end{abstract}
\selectlanguage{english}
\chapter{Introduction}
\hypersetup{ linkcolor = [rgb]{0,0.5,0} }
\renewcommand{\arraystretch}{1.5}
\pagenumbering{arabic}
\fancypagestyle{plain}{
\renewcommand{\headrulewidth}{0pt} \renewcommand{\footrulewidth}{0pt} }
\rowcolors{2}{gray!20}{white}
%% W opisie warto dodac uzupelnienie - wyjasnienie szerokiego podloza problemu,
%% ktory jest glownym tematem. Moznaby zacząc od kwestii problemu "supply chain
%% management" w ogolnosci (w gospodarce) - wymienic problemy, troski, obawy i
%% potrzeby.
Most products of modern industry are composed or made using a number of
half-products and tools. These tend to come from different producers, who
themselves rely on their suppliers. Such half-products might be produced with
violations of human rights, unecologically, without meeting certain quality
standards, or with patent violations. The assembly from half-products also
creates an opportunity for deliberate sabotage on part of the supplier. So far
businesses have not always successfully mitigated these threats, which later
reverberated in many ways.
%% W kolejnym akapicie podac krotką charakterystyki problemow z tym związanych,
%% ale juz w kontekscie procesu wytworczego oprogramowania (powtorzyc istotne
%% zagadnienia "supply ..." lub uszczegolowic)
Just as a design is often used to manufacture physical products, code written in
a programming language is used to produce software in its target form, e.g., an
executable, a firmware image, or a collection of files. This process of
producing software in its target form can be referred to as software
\textbf{build}. Items resulting from it are \textbf{build outputs}. A software
build process overview is presented in Figure~\ref{fig:build-process-overview}.
Depending on the programming languages and technologies in use, the build might
encompass different actions, e.g., macro processing, compilation, linking,
bundling, or compressed archive creation. It can also utilize a multitude of
different tools. Adjusting the build process to meet certain requirements is
often a complex task that requires understanding the workings of various tools
involved. In some software distribution projects, hundreds of lines of scripts
are maintained to allow proper building of a single piece of software written by
another party. Builds can even involve applying changes to upstream code, often
through the use of patches, i.e., machine-readable files describing changes to
project code.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{build-process-overview.svg}
\caption{Overview of a sample software build process.}
\label{fig:build-process-overview}
\end{figure}
Similarly to physical products, software is made using preexisting elements
delivered by other parties. These are often called \textbf{dependencies}. They
include
\begin{itemize}
\item
runtime dependencies -- components to be distributed inside or alognside the
final program and used during its execution, for example reusable modules of
code called libraries or special fonts, and
\item
development dependencies -- elements not needed during program's execution but
useful to its developers, furter classifiable as
\begin{itemize}
\item
build dependencies -- compilers, linkers, test frameworks, etc.\ needed in
the build process, typically able to function non-intereactively and invoked
through some layer of automation, sometimes categorized further, for example
into native and non-native or into build and test dependencies, and
\item other development tools -- tools to work with software that are not
needed in the actual build process, more often manually-operated, like
IDEs\footnote{Integrated Development Environments} and their plugins,
debuggers, or linters.
\end{itemize}
\end{itemize}
\section{Problem formulation}
\textbf{If either an external dependency suffers from contamination, the
infrastructure handling the build is compromised, or the organization or
individuals attempt a sabotage, then a backdoor or other security
vulnerability can be implanted in the software being built. In a basic
setting, each dependency, the infrastructure, and the organization are all
single points of failure. The last two of these points can be secured through
additional build outputs verification that utilizes software reproducibility.
This work aims at exploiting reproducibility to secure software's build
process, with special focus on eliminating the gaps that would leave single
points of failure.}
A reproducible build is one that produces the same, bit-to-bit identical outputs
when repeated. For example, the resulting program executables are bit-to-bit
identical. This concept assumes that a set of \textbf{build inputs} with the
same contents is used in every repetition. E.g., program sources and
dependencies in exact same versions are used. As a consequence, one
prerequisite of reproducibility is \textbf{hermeticity} -- the quality of a
build process that depends exclusively on a set of predefined dependencies. A
hermetic build must not depend on changeable network resources nor on machine's
installed software other than build's formal inputs. Hermeticity is usually
ensured by performing software build inside a minimal, isolated environment,
often a container utilizing Linux namespaces.
Multiparty verification of build's reproducible output can help increase
confidence that built software is not contaminated due to compromise of
infrastructure underpinning the build environment nor malicious actions of
infrastructure operators. The verification shall be unsuccessful if the
contamination is present in an output of one build and not in those of the
others. The overviews of successful and unsuccessful verification performed by
end user -- a scheme that does not create unnecessary single points of failure
-- are presented in Figures \ref{fig:rebuilds-no-contamination-diagram}
and~\ref{fig:rebuilds-contamination-diagram}, respectively. Contamination is
represented by a frowning face. The extra confidence coming from verification
can empower both software vendors willing to reduce the risk of distributing
compromised code and software consumers wanting to secure their operations.
\begin{figure}[htpb]
\centering
\includesvg[
width=\linewidth,
inkscapelatex=false
]{rebuilds-no-contamination-diagram.svg}
\caption{Overview of a successful multiparty build verification process.}
\label{fig:rebuilds-no-contamination-diagram}
\end{figure}
\begin{figure}[htpb]
\centering
\includesvg[
width=\linewidth,
inkscapelatex=false
]{rebuilds-contamination-diagram.svg}
\caption{Overview of an unsuccessful build verification process.}
\label{fig:rebuilds-contamination-diagram}
\end{figure}
Single-party verification is also applicable if only the infrastructure threats
are considered. Meanwhile, the party itself retains the ability to undetectably
compromise software builds, i.e., implant backdoors. Figure
~\ref{fig:rebuilds-contamination-1party} depicts an occurrence of such
compromise while single-party verification of build's reproducible output is
taking place. Contamination is represented by a frowning face.
In addition to the above, just as reproducible builds performed by a single
organization are insufficient to protect from contamination introduced
deterministically by the organization, reproducible builds performed on a single
infrastructure would be insufficient to protect from contamination spreading
deterministically from that infrastructure.
\begin{figure}[htpb]
\centering
\includesvg[
width=\linewidth,
inkscapelatex=false
]{rebuilds-contamination-1party.svg}
\caption{Overview of a build verification process which only compared the
outputs of builds performed by a single party and failed to detect malice.}
\label{fig:rebuilds-contamination-1party}
\end{figure}
For software to be secured with reproducible builds, its build process has to
gain the quality of reproducibility, where repetition of the same build produces
output without variations. Achieving that quality can itself be challenging.
This involves identification of sources of build process' nondeterminism -- like
timestamps and a changing order of filenames in directory listings. Identified
sources need to be removed, e.g., by use of fixed date in timestamps or sorting
of filenames obtained from directory scans. Achieving this is nowadays easier
because common sources of nondeterminism have already been investigated and
workarounds have been implemented. For example, since version 7 the GNU C
Compiler checks for the existence of a \code{SOURCE\_DATE\_EPOCH} environment
variable containing a time value. It automatically uses this value in generated
file timestamps~\cite{source-date-epoch}. Additionally, dedicated tooling for
investigating non-reproducibility issues has been developed, notably the
\textbf{diffoscope} program~\cite{DBLP:journals/corr/abs-2104-06020}. To
decrease the chance of contamination from a compromized operating system,
firmware, and hardware, the actual build -- once its reproducibility issues are
resolved -- should be performed on infrastructures that differ as much as
possible, except for the invariant set of build inputs and environment
configuration needed to ensure reproducibile outputs.
This work does not address the challenges of avoiding nondeterminism in software
builds. Instead, the work's goal is to ensure that -- in practical scenarios --
the build inputs remain invariant in all build repetition attempts. The work's
second major concern is that all machine-performed operations -- even those
deemed preparatory -- can have their effect on build output controlled through
reproducibility. All of this, in turn, can make reproducible builds a more
reliable and more complete security mechanism.
Despite their benefits, one should nevertheless realize that reproducible builds
only address a particular subset of software supply chain threats -- ones
affecting the build process -- and are mostly useful if other stages of that
chain are also secured. Some of the practices that can help with this are
\begin{enumerate}
\item
making sure the software sources relied upon are audited against backdoors, at
least informally, e.g., by the virtue of being developed in the Bazaar model,
where the public has a high chance of noticing malicious
changes~\cite{raymond2001cathedral},
\item
making sure the software sources do not get altered by any party after the
verification from the step above, and
\item
using reproducible builds and other mechanisms to verify software's
dependencies, possibly recursively.
\end{enumerate}
One example of a threat not remediated through reproducible builds alone is the
loud XZ backdoor from 2024. Among others, it targeted Debian and Fedora
software distributions. Backdoor's activation code was only present in the
official source release archives and not in the source repository, which is most
often looked at by programmers~\cite{journals/corr/abs-2404-08987}. When the
software was built from source archives, it had backdoor code linked in, but
build results were deterministic. Attacks in such form would not be possible if
the source archives were verified to correspond to version-controlled software
sources.
\chapter{Contemporary guidance and standards in the field of software supply
chain security}
Threats related to software build and delivery process were known already long
ago. One interesting self-implanting compiler backdoor was described by Ken
Thompson in his Turing Award lecture in 1984, ``Reflections on Trusting
Trust''~\cite{Thompson:1984}. Later signs of interest in supply chain threats
in certain circles include for example David A.\ Wheeler's PhD dissertation
titled ``Fully Countering Trusting Trust through Diverse Double-Compiling''
\cite{phd/basesearch/Wheeler09a} and eventually Bitcoin's use of Gitian
deterministic builder\footnote{before replacing Gitian with GNU Guix in 2021}.
Also, for many years certain software distributions have been compiling their
software from sources on dedicated servers, in isolated environments with only
mininum dependencies for a given build. One example of such distribution is
Debian.
At the same time, for a wide public it's been a norm to rely on prebuilt
software that gives virtually no guarantees that it was built in a secure
environment. Multiple software repositories
% like npm Registry and PyPI\footnote{Python Package Index}
allow publishing developer-built software packages. Such software -- built from
a valid VCS\footnote{version control system} checkout but on developer's
infected machine -- could be maliciously modified and distributed to unaware
software integrators wishing to utilize it in their projects. Neither
cryptographic signing of packages nor VCS source code audits would mitigate such
attacks.
Several spectacular supply chain attacks of recent years became the catalyst of
work towards increasing the level of security. In case of the SolarWinds attack
from 2020, also known under the name Sunburst, software distributed among
reportedly more than $18\,000$ customers turned out to contain a backdoor
implanted after a compromise of vendor's
infrastructure~\cite{conf/uic/SterleB21}. It was exactly the kind of threat
that reproducible builds address. As a result of the event, SolarWinds
Corporation suffered great economic losses and pejoration of its brand's image.
Additionally, the company exposed thousands of customers to cyberattacks
leveraging its compromised software. All of this could have been avoided
through reproducible verification of software build outputs.
As more attacks on software build and distribution are reported, software supply
chain security becomes a hot topic. It attracts the attention of public
institutions and private organizations alike. Some prominent undertakings by
nonprofits are: launch of OWASP's\footnote{Open Worldwide Application Security
Project} SCVS\footnote{Software Component Verification Standard} in 2019,
foundation of OpenSSF\footnote{Open Source Security Foundation} in 2020, launch
of its SLSA\footnote{Supply Chain Levels for Software Artifacts} framework in
2021, Microsoft's donation of S2C2F\footnote{Secure Supply Chain Consumption
Framework} to OpenSSF in 2022, as well as the publishing of
CNCF's\footnote{Cloud Native Computing Foundation, a project of Linux
Foundation} ``Software Supply Chain Best Practices'' in 2021. State actors also
took voice by the means of ``Securing the Software Supply Chain: Recommended
Practices for Developers'' and subsequent two guides from 2022 developed by the
ESF\footnote{Enduring Security Framework} partnership with support from
CISA\footnote{Cybersecurity and Infrastructure Security Agency}, the
NSA\footnote{National Security Agency}, and the Office of the Director of
National Intelligence. Another possibly relevant document is NSA's
``Recommendations for Software Bill of Materials (SBOM) Management'' from 2023.
\section{Software Component Verification Standard}
SCVS \cite{owasp-scvs} describes itself as a ``community-driven effort to
establish a framework for identifying activities, controls, and best practices,
which can help in identifying and reducing risk in a software supply chain''.
Despite being developed by OWASP it is generic and not limited to web
applications in its scope. Authors recognize the unfeasibility of applying all
good practices and threat mitigations at every phase of every software project
and categorize their security requirements into three levels, each implying the
previous one and extending it.
Practices listed in SCVS are grouped into six topics and formulated briefly.
They are agnostic about the technology stack and data formats in use. At length
explanation of the importance of prescribed actions is not part of the document.
As of version 1.0 of the standard, level 2 requirements include a method to
locate ``specific source codes in version control'' that correspond to a given
version of a third-party package from software repository. While it is stated
that the correspondence must be verifiable, further details are not given.
SBOM\footnote{software bill of materials} and repeatable build process are
required for an application being developed but not for third-party components.
Additionally, listed practices regarding the build environment mention neither
the goal of reproducibility nor the weaker hermeticity. While authors might
have -- justifiably -- judged such rules as unfeasible given the current state
of the software ecosystem, it is interesting from the point of view of this
work. Threats that could not be addressed a few years ago in a generic setting
might be remediable now in the context of one or several technology stacks.
\section{Supply Chain Levels for Software Artifacts}
SLSA \cite{slsa} uses similar but conceptually more complex categorization than
SCVS. Practices are going to be assigned to so-called ``tracks'' which
correspond to different aspects of software supply chain security and which
might use different numbers of security levels. As of framwork version 1.0
there only exists a ``Build'' track with three levels, not counting the empty
zeroth level. In addition to the specification of requirements, SLSA documents
different threats grouped into those concerning the source, dependencies, build,
availability, and verification of an artifact. Historical examples of attacks
using some of these techniques are listed in the documentation. Finally, it
also includes instructions how to apply SLSA and how to use it with attestation
formats from the in-toto framework~\cite{conf/uss/Torres-AriasAKC19}.
Many aspects of the build process are addressed in the specified requirements
set but the qualities of hermeticity and reproducibility were removed from the
set at the drafting stage. SLSA explicitly calls verified reproducible builds
one of multiple methods of implementing the requirements. In the context of the
particular threat of compromised infrastructure, framework's focus is instead on
stronger security controls for the build platform. The platform, however,
remains a single point of failure. Incidents like that of SolarWinds could
still occur. Reproducibility and hermeticity might be re-introduced in
subsequent revisions of SLSA, as explained on its ``Future directions'' page.
The specification currently also does not cover the recursive application of its
requirements to input artifacts used. It is nonetheless suggested that users
could apply SLSA independently to transitive dependencies. This approach is
presented as a possible mitigation to attacks like that performed on
event-stream library in 2018.
\section{Secure Supply Chain Consumption Framework}
S2C2F \cite{s2c2f} is complementary to SLSA in that it embraces software
consumer's point of view. It introduces four ``levels of maturity'' of
requirements with the highest level mandating a consumer-performed rebuild of
all artifacts. Having the artifact built reproducibly by several third parties
is mentioned as an alternative approach. Neither method is presented as more
secure, even though local rebuild still suffers from being a single point of
failure.
\section{``Software Supply Chain Best Practices''}
As of version 1, this paper \cite{cncf-sscp} recognizes three categories of risk
environments and three categories of assurance requirements. These are -- in
both cases -- ``low'', ``moderate'', and ``high''. A methodology for securing
the software supply chain is presented in five stages, with four themes of
``Verification'', ``Automation'', ``Authorization in Controlled Environments'',
and ``Secure Authentication'' being repeated in them. Recommendations are
organized into paragraphs rather than tables or lists. Authors point towards
existing tools useful for some of the tasks, notably the in-toto
framwork~\cite{conf/uss/Torres-AriasAKC19} and Rebuilderd
system~\cite{drexel2025reproduciblebuildsinsightsindependent}. At the same
time, they openly admit that some of the practices they describe might require
extra effort to implement because certain challenges have not yet been countered
by the supply chain industry.
Reproducible builds are presented as potentially leverageable when high
assurance is needed. The topic is discussed in more detail than in the previous
documents from OWASP and OpenSSF. In addition, hermeticity is included as a
recommendation for high-risk and high-assurance environments. Recursive
dependencies are treated with equal care to the direct ones, consistently with
authors' statement that ``a supply chain's security is defined by its weakest
link''. The issue of bootstrapping a system image for builds is also discussed
in the paper.
\section{``Securing the Software Supply Chain: Recommended Practices Guide''}
The series was developed by a public-private working group with members from
both the industry and U.S.\ government agencies. It is described as
informational only and does not define any standard. Subsequent parts are
addressed at software developers, suppliers -- who are considered to be
``liaising between the customer and software developer'' -- and customers.
Although these series do not group recommendations into levels, two mitigations
in the first guide from August 2022 \cite{nsa-esf-recommended-practices-devs}
are called ``advanced'' and described as providing ``additional protection''.
These are the hermetic and reproducible builds. A suggestion is made that the
same builds are performed ``in both cloud and on-premise environments'' and
their outputs compared. Additionally, authors state a justification should be
required when it is impossible to perform certain build reproducibly. The text
of this requirement has been copied verbatim from SLSA draft back before being
removed there.
The guide also recommends that images used to deploy the build environment
should be created from sources except where ``there is an understanding of the
provenance and trust of delivery''. No statements explicitly concerning
rebuilds of transitive dependencies of a product are made.
\section{``Recommendations for SBOM Management''}
\label{sec:recommendations-for-sbom}
The paper \cite{nsa-sbom-management} calls itself a guidance. It lists
recommendations for general software suppliers and consumers but also dedicates
a big part to users and owners of NSS\footnote{U.S.\ national security systems
-- a specific category of information systems used on behalf of U.S.\ agencies}.
Document's primary focus is on functionalities that tools used to manage SBOMs
should provide.
NSA's guidance concerns SBOMs, which hold information about software components
comprising final product. The guidance does not directly address build process
threats and does not touch the topics of reproducibility and transitive
dependencies of software. In fact, the industry recognizes another type of bill
of materials, not mentioned in the document, which is more relevant to the topic
of reproducibility than SBOM. It is manufacturing bill of materials. In the
context of software, MBOM conveys information about all components needed for
its build. This also includes project's build dependencies which would not be
recorded in an SBOM. MBOMs are relevant from reproducibility perspective
because information in them can make software rebuilds possible. Even though
MBOMs are not directly mentioned in version 1.1 of NSA's guidance, one of the
recommendations present there is labeled as ``Scalable architecture''. It is
described as one that can also ``handle other types of BOMs''.
\section{Summary}
Published documents' attitutes to reproducibility and hermeticity range from
agnosticism to suggestion and recommendation in the context of certain
environments. Reproducibility and its requisite -- hermeticity -- are difficult
to achieve with a great subset of existing popular software projects. This
difficulty might stand behind the limited focus on these measures in documents
other than CNCF's ``Software Supply Chain Best Practices''. It appears that the
means of securing the software supply chain which are more straightforward to
employ are also more often recommended. In such case, making reproducibility
easier to achieve for all kinds of software projects should lead to it being
more frequently discussed and therefore more broadly leveraged.
\chapter{Security tools leveraging reproducible builds}
\label{chp:existing-security-tools}
Several initiatives and pieces of software exist that are concerned with the
verification of reproducibility of software packages. The champion of these
efforts is the Reproducible Builds project, also affiliated with Debian.
\section{in-toto apt-transport for Debian packages}
in-toto framework, developed under the CNCF, aims to secure the integrity of
software supply chains~\cite{conf/uss/Torres-AriasAKC19}. Debian GNU/Linux is
an operating system distribution founded in 1993. It provides thousands of
pieces of software in form of \textbf{packages} that can be installed in the
system via Debian's package manager, APT\footnote{Advanced Package Tool}.
In 2018 it became possible to use in-toto together with Debian's APT, to verify
that a package being installed has been verified through reproducible builds.
The package manager can be configured to abort installation if the package was
not reproduced by at least $k$ independent rebuilders, with $k$ configurable by
the user. In the process, cryptographically signed attestations of rebuilt
packages are fetched over the network from rebuilder URIs that are also
configured by the user.
\subsection{How a Debian package is made and rebuilt}
\label{sub:how-debian-package-is-made}
Most packages available in Debian contain software written by third parties,
i.e., the \textbf{upstream}. That software was released in source form and
subsequently integrated into Debian. A package typically has a maintainer who
is a Debian volunteer taking care of the package, possibly with the aid of other
people~\cite[Chapter~1]{debian-new-maintainers-guide}.
Upon initial creation or a version update of a Debian package, its maintainer
first prepares what is called a \textbf{source package}. It is the primary
input of the build process that will produce the final, installable package.
The installable package is also sometimes called a \textbf{binary package} to
distinguish it from the source package. A single build process with a single
source package can also prouce multiple binary packages. For example, a
programming library written in the C programming language can have its
dynamically linked binary and its header files placed in distinct binary
packages. As of \debianTresholdDate{}, the current release of Debian -- Debian
12, codenamed ``Bookworm'' -- offered $63\,465$ packages for x86\_64
architecture, as found in its \code{main} pool. They were produced from
$34\,217$ source packages.
%% This is actually 38,546 buildinfo files and this many builds -- because
%% separates builds are conducted with a single source pacakge to produce
%% architecture-specific and architecture-independent outputs…
%% gawk '
%% BEGIN{
%% delete registered_builds[""];
%% }
%% /^Package:/{
%% source = 0;
%% ver = 0;
%% arch = 0;
%% }
%% /^Source:/{
%% source = $2;
%% }
%% /^Source:.*[(].*[)]/{
%% ver = gensub("Source: .*[(](.*)[)]", "\\1", 1);
%% }
%% /^Architecture:/{
%% arch = $2;
%% }
%% /^Filename:/{
%% prefix_dir = gensub("Filename: pool/main/([^/]+).*", "\\1", 1);
%% if (!source) {
%% source = gensub("Filename: pool/main/[^/]+/([^_/]+).*", "\\1", 1);
%% }
%% if (!ver) {
%% ver = gensub("[^_]+_([^_]+).*", "\\1", 1);
%% }
%% source_id = source "_" ver;
%% build_id = source_id "_" arch;
%% dir_url = "https://buildinfos.debian.net/buildinfo-pool/" \
%% prefix_dir "/" source
%% url = dir_url "/" build_id ".buildinfo";
%% if (!(build_id in registered_builds)) {
%% print source_id " " build_id " " url;
%% registered_builds[build_id] = 1;
%% alt_url = dir_url "/" build_id "-source.buildinfo";
%% print source_id " " build_id " " alt_url;
%% }
%% }
%% ' Packages > buildinfo-urls
%% gawk '{print $1}' buildinfo-urls | sort | uniq | wc -l
%% mkdir -p buildinfos
%% process_line() {
%% local SOURCE_ID=$1
%% local BUILD_ID=$2
%% local URL=$3
%% if [ ! -e buildinfos/$BUILD_ID.buildinfo ]; then
%% if [ -e buildinfos-dumb/$BUILD_ID.buildinfo ]; then
%% mv buildinfos-dumb/$BUILD_ID.buildinfo buildinfos/$BUILD_ID.buildinfo;
%% else
%% wget --no-verbose -O buildinfos/$BUILD_ID.buildinfo $URL \
%% >> buildinfos-download.log
%% fi
%% fi
%% }
%% while read LINE; do
%% process_line $LINE;
%% done < buildinfo-urls
An official Debian source package typically consists of
\begin{enumerate}
\item
software sources taken from the upstream -- possibly with inappropriately
licensed components removed and other changes applied to meet Debian
guidelines -- taking form of one or more compressed archives,
\item
package's recipe, taking form of a compressed archive, including, among others,
\begin{itemize}
\item
a list of software's build and runtime dependencies, placed -- with other
metadata -- in a file named \code{debian-control}, with an example in
Listing~\ref{lst:debian-control-excerpts},
\item
optional patch files that describe Debian-specific changes which are to be
applied to upstream software as part of the automated build process, with an
example in Listing~\ref{lst:debian-shc-patch}, and
\item
a script directing the build process, placed in a file named
\code{debian/rules}, invoked as a Makefile, with an example in
Listing~\ref{lst:debian-rules-excerpt}, and
\end{itemize}
\item
a text file with \code{.dsc} suffix containing cryptographically signed source
package metadata, including hashes of compressed archives from the above
points.
\end{enumerate}
\lstinputlisting[
float=htpb,
caption=Excerpts from a $176$-lines long \code{debian/control} file of the
\code{nodejs} Debian package.,
label=lst:debian-control-excerpts,
numbers=none
]{debian-control-excerpt.txt}
\lstinputlisting[
float=htpb,
language=shc-patch,
caption={A patch used by Debian package \code{shc} to provide an upstream
script with the correct path of the \code{rc} executable, as present in
Debian.},
label=lst:debian-shc-patch
]{debian-shc.patch}
\lstinputlisting[
float=htpb,
caption=Excerpt from a $2045$-lines long \code{debian/rules} Makefile of the
\code{binutils} Debian package.,
label=lst:debian-rules-excerpt,
numbers=none
]{debian-rules-excerpt.txt}
The package maintainer is likely to perform one or several builds when working
on a new or updated source package. However, except for special cases, it is
only the source package and not the maintainer-built binary packages that gets
uploaded to what is called the \textbf{Debian archive}. Uploaded source
packages are ``built automatically by the build daemons in a controlled and
predictable environment''~\cite[Chapter~5]{debian03developers}.
Besides producing binary packages, the build daemons also record the metadata of
performed builds, which is later published with cryptographic signatures as
\code{.buildinfo} files\footnote{which can be considered a type of MBOM that was
described in \ref{sec:recommendations-for-sbom}}. For a given binary package,
it is usually possible to locate and download its corresponding
\code{.buildinfo} file. That file contains, among others, a list of names and
versions of Debian packages that were installed in the minimal build
environment. An example of a \code{.buildinfo} file is shown in Listing
\ref{lst:haskell-sth-buildinfo-excerpts}.
\lstinputlisting[
float=htpb,
caption=Excerpt from a $256$-lines long \code{.buildinfo} file of the
\code{haskell-base-compat-batteries} Debian package.,
label=lst:haskell-sth-buildinfo-excerpts,
numbers=none
]{haskell-sth-buildinfo-excerpts.txt}
The \code{.buildinfo} files can be used by parties other that The Debian
Project to rebuild the official packages, write in-toto metadata of the process,
sign it, and subsequently serve it to the users.
\section{\code{guix challenge} command of GNU Guix}
GNU Guix is an operating system distribution and a package manager that appeared
in 2013~\cite{conf/els/Courtes13}. It implements functional package management
model described by Eelco Dolstra in ``The Purely Functional Software Deployment
Model'' in 2006 \cite{phd/basesearch/Dolstra06} and pioneered by Nix package
manager. For avoidance of confusion with an unrelated ``GUIX'' U.S.\ trademark
registered in 2019 and owned by Microsoft, the GNU Guix package manager shall be
referred to with its ``GNU'' prefix throughout this document.
Similarly to Debian, GNU Guix relies on software written by upstream authors and
makes it available in the form of installable packages. However, the data
formats, build mechanisms, and nomenclature differ. The equivalent of Debian's
binary package is referred to as a \textbf{substitute}. Since 2015, GNU Guix
provides a \code{guix challenge} command which ``allows users to challenge
the authenticity of substitutes provided by a
server''~\cite{gnu-guix-0.9.0-released}. End users can invoke this command to
compare the outputs of package builds performed on multiple infrastructures and
report which packages were not built reproducibly -- either due to
nondeterminism of the build process or because of build's compromise.
\subsection{How a GNU Guix package is made and built}
\label{sub:how-gnu-guix-package-is-made}
GNU Guix package collection is determined by a set of package recipes. Unlike
Debian package recipes, these do not take the form of compressed achives. Here,
packages are defined in Scheme programming language from Lisp family. A recipe
consists of code that instantiates and populates a \code{<package>} data
structure representing a package that can be built. Recipe's code can use the
facilities of the Turing-complete Scheme programming language to dynamically
compute parts of this new \code{<package>} instance. A \code{<package>}
instance does -- in most cases -- get bound to a Scheme variable, which other
recipes' code can reference. Lists of package's explicit build and runtime
dependencies are typically constructed using references to other package
variables. A package recipe example is shown in Listing
\ref{lst:guix-python-axolotl-package}. It defines a variable of the same name
as the package and declares its explicit dependencies by referencing
\code{python-protobuf} and other two package variables. A Scheme code snippet
is supplied to be executed during the hermetic build process. It customizes the
process by deleting unnecessary files.
\lstinputlisting[
float=htpb,
language=guix-package-definition,
caption=Recipe of \code{python-axolotl} GNU Guix package.,
label=lst:guix-python-axolotl-package,
numbers=none
]{guix-python-axolotl-package.scm}
The recipes of all official GNU Guix packages are kept and maintained in a
single VCS repository. As of \tresholdDate{}, this is a repository that houses
both the recipes collection and the GNU Guix application, although this setup is
not imposed by design and might change in the future. Recipes in the repository
can also have accompanying patch files. However, patches are used less
frequently here than in Debian package recipes. Regular expression
substitutions performed by Scheme code are preferred by GNU Guix developers for
trivial modifications of upstream source.
Package recipes in GNU Guix generally reference remote software sources using
URLs and hashes that are considered cryptographically secure. The hashes are
used for verification of sources' integrity upon download and make it possible
to safely download them from fallback servers, among which is the archive of
Software Heritage \cite{journals/corr/abs-2405-15516}. Several remote resource
formats are supported, including traditional compressed archives as well as
repositories of popular VCSes. Referencing VSC repositories of upstream
projects -- although not practiced universally in the recipes collection --
allows the correspondence of build inputs to public-reviewed sources to be more
easily tracked.
The GNU Guix package manager is able to build packages locally, on the system on
which their installation was requested. Each deployment of GNU Guix comes -- by
design -- with a copy of the recipes collection, such that only the source
inputs -- identified by cryptographic hashes -- need to be downloaded for a
build to be performed. Local builds are fully automated, are performed in
isolated environments created in the background and are a first-class citizen in
the model of GNU Guix. For practical reasons, it is made possible to instead
download prebuilt packages -- the substitutes that substitute their
locally-built equivalents.
The \code{guix challenge} command allows the build outputs advertised by
configured substitute servers to be compared with each other and with the
outputs of local builds, when available.
Lack of automatized integration of reproducibility verification with package
deployment is a notable limitation of the \code{guix challenge} command of GNU
Guix. The command has to be invoked explicitly by the user. As of
\tresholdDate{}, there is no official way to \textbf{automatically} challenge
the binary substitutes that GNU Guix downloads as part of other actions, such as
software installation. Thus, in practice, the command is less easily usable as
an end user's preventive security tool and more as an investigation and internal
verification aid.
Bitcoin Core, possibly the most famous piece of software using GNU Guix to
reproducibly verify its binaries, does not rely on the
\code{guix challenge} command and instead uses its own custom scripts to
perform code signing.
\section{Continuous tests}
The tools presented so far allow the end users to verify binaries before they
are put in use. The user can first learn whether a set of software packages was
rebuilt with bit-to-bit identical results on independent infrastructure and can
then make an informed decision whether to install the packages. The benefit of
this type of verification is that it leaves no single point of failure, except
for end user's device. However, if the latter were compromised in the first
place, no software-based scheme would reliably remediate that. This scenario is
therefore out of scope of this work.
The drawback of this type of verification is that accidential
non-reproducibility due to an overlooked source of nondeterminism in the build
process leads to verification failures, as depicted in
Figure~\ref{fig:rebuilds-inconclusive-diagram}. A lag of independent rebuilders
can likewise make verification impossible, as also shown in the figure. If
reproducible builds are to be used as a preventive security measure, any such
failure would need to stop the end user from performing the attempted software
installation or update. Until the percentage of reproducibly buildable software
in distributions is close to 100\% and enough resources are invested in
independent infrastructure performing continuous rebuilding, this problem can be
prohibitive.
\begin{figure}[htpb]
\centering
\includesvg[
width=\linewidth,
inkscapelatex=false
]{rebuilds-inconclusive-diagram.svg}
\caption{Overview of a verification process inconclusive due to rebuilder's
delay and lack of determinism.}
\label{fig:rebuilds-inconclusive-diagram}
\end{figure}
However, there are several projects where verification of reproducibility is
performed by someone else than the end user. Although this does not eliminate
the single point of failure from software installation process, such
verification can still make supply chain attacks harder. For example, if an
organization performs internal tests of reproducibility and analyzes their
results, it is more likely to detect code contamination early on and react to
it.
As of \debianTresholdDate{}, the Reproducible Builds project performs continuous
tests of the reproducibility of
\begin{itemize}
\item files from coreboot, FreeBSD, NetBSD, and OpenWrt projects, as well as
\item packages from Debian repositories, with package reproducibility statistics
being reported, as in Figure~\ref{fig:bookworm-stats-pkg-state}.
\end{itemize}
\begin{figure}[htpb]
\centering
\includegraphics[width=\linewidth]{bookworm-stats-pkg-state.png}
\caption{Reproducibility of Debian Bookworm packages over time, as presented on
Reproducible Builds' continuous tests website.}
\label{fig:bookworm-stats-pkg-state}
\end{figure}
As of \debianTresholdDate{}, $33\,214$ source packages from Debian Bookworm were
reported to have been rebuilt reproducibly for the x86\_64 architecture. That
means approximately 97\% reproducibility in the collection. The remaining
packages either could not be built on the Reproducible Builds infrastructure,
with various possible reasons, or were built with outputs differing on binary
level.
The Reproducible Builds project also lists several others -- including GNU Guix
mentioned earlier and its predecessor NixOS -- that monitor the reproducibility
of their files and/or repository packages without relying on the Reproducible
Builds' infrastructure~\cite{reproducible-builds-continuous}. One notable
undertaking in this category is the development of Rebuilderd tool for
reproducible rebuilds of packages from Arch Linux and recently other
distributions~\cite{drexel2025reproduciblebuildsinsightsindependent}. An
application also exists that can consult a Rebuilderd instance to automatically
verify packages installed in user's Arch Linux system~\cite{archlinux-repro}.
The continuous tests platform used by GNU Guix is capable of generating
reproducibility reports, which are viewable on pages at
\url{https://data.guix.gnu.org}. Part of such report is shown in
Figure~\ref{fig:guix-pkg-repro-stats}. According to it, there were $39\,344$
packages available for the x86\_64 architecture as of \tresholdDateAndCommit{}.
$35\,415$ of them -- approximately 90\% -- were rebuilt reproducibly, albeit
with $2\,087$ remaining untested. Frequent package updates and builders' lag
are possible reasons for the large number of untested packages. Out of all the
successfully rebuilt GNU Guix packages, approximately 95\% had outputs that were
bit-to-bit identical with those produced on another infrastructure.
\begin{figure}[htpb]
\centering
\includegraphics[width=\linewidth]{guix-pkg-repro-stats.png}
\caption{Reproducibility of GNU Guix packages as reported by its continuous
tests platform.}
\label{fig:guix-pkg-repro-stats}
\end{figure}
Unfortunately, several of the reproducibility tests listed on the Reproducible
Builds website have become unmaintained. The testing for Fedora and Alpine
operating system distributions was disabled at some point. Although the
reproducibility statistics of GNU Guix packages are still delivered, their web
pages sometimes cannot be viewed due to timeouts, as also witnessed by Internet
Archive's Wayback
Machine\footnote{\url{https://web.archive.org/web/20250625124729/https://data.guix.gnu.org/repository/1/branch/master/latest-processed-revision/package-reproducibility}}.
\chapter{Applicability of reproducibility workflows to different software ecosystems}
\label{chp:applicability-of-workflows}
Current reproducible software distributions, like GNU Guix and Debian, are
\textbf{system software distributions} -- ones that contain a collection of
packages that can form a complete operating system. As such, a mixture of
software technologies can be found in them.
Certain programming languages and computing platforms form software ecosystems
centered around them, for instance, the ecosystem of the Python programming
language with CPython\footnote{the most popular implementation of the Python
programming language, written in C} and PyPy being its most popular runtimes.
These ecosystems evolve their specific software package formats and workflows
for building these packages. Many popular ecosystems have their dedicated
package repositories that usually serve as primary distribution channels of
software written for the ecosystem's computing platform. Such
ecosystem-specific software repositories are often, although imprecisely,
referred to as language-specific repositories. They are typically open to the
public for registration and package creation. As such, they form environments
of software with varying levels of quality and significance.
Many ecosystem-specific repositories distribute software without all the
metadata that is necessary to automate rebuilding it. Moreover, if a project
uses multiple packages from such repository, it relies on security of each of
the machines used by these packages' developers for builds and uploads. A
partial remedy -- facility to publish packages together with build provenance
data cryptographically signed by a build service -- was employed by
ecosystem-specific repositories \textbf{npm Registry} and
\textbf{PyPI}\footnote{Python Package Index} in 2023 and 2024, respectively. A
dedicated build service -- with the most popular ones being GitHub Actions and
GitLab CI/CD -- can be considered better secured than an average developer's
computer, for the benefit of packages that are confirmed to have been built
there. In addition, build provenance data identifies the source repository used
in the build. However, even when secured, build service remains a single point
of failure of the process. In addition, support for only one or few selected
build services -- as offered by the npm Registry as of \tresholdDate{} -- leads
to vendor lock-in.
\section{Degree of inclusion in Debian and GNU Guix}
Software utilizing the respective computing platforms and distributed primarily
through an ecosystem-specific software repository might, at some point, also get
included in a system software distribution. However, so far it did not happen
with certain popular and strategic pieces of software. One example is Electron
framework that is used, among others, by Signal application and Visual Studio
Code IDEs. As of \tresholdDate{}, Electron is declared a development dependency
by $4\,533$ packages in the npm Registry. At the same time, software
distributions that test for package reproducibility usually lack Electron and
Electron-based applications, as do Debian and GNU Guix. Another software
distribution that tests for package reproducibility, NixOS, redistributes
Electron's upstream binaries without actually building the software. In this
case, the build itself is not being verified through reproducibility.
Certain programming languages and computing platforms have seen more packaging
progress in system software distributions. Let us consider the PyPI, npm, and
crates ecosystems, which are centered around their respective repositories and
technologies, as shown in Table \ref{tab:software-ecosystems}. For this work,
repositories were chosen as a basis for distinguishing the ecosystems. It is a
feasible criterion, although not the only possible one. There are overlaps of
various sizes between different repositories, runtimes, and project management
tools. Also, in some cases a software package has formal of informal
dependencies that are not distributed through the reposotory that the package
itself uses.
\begin{table}[htpb]
\caption{Considered software ecosystems.}
\centering
\label{tab:software-ecosystems}
\footnotesize
\columnsCount{4}
\begin{tabular}{
>{\raggedright\arraybackslash}p{.31\netTableWidth}
>{\raggedright\arraybackslash}p{.23\netTableWidth}
>{\raggedright\arraybackslash}p{.23\netTableWidth}
>{\raggedright\arraybackslash}p{.23\netTableWidth}
}
\rowcolor{gray!40}
&
\textbf{PyPI} &
\textbf{npm} &
\textbf{crates} \\
\textbf{repository} &
PyPI &
npm Registry &
crates.io \\
\textbf{{primary} \mbox{programming} \mbox{languages}} &
\cellitems \item Python, \item Cython &
\cellitems \item JavaScript, \item TypeScript, \item WASM &
\cellitems \item Rust \\
\textbf{\mbox{sample} \mbox{runtimes} or \mbox{compilers}} &
\cellitems \item CPython, \item PyPy\ &
\cellitems \item Node.js, \item Deno, \item Bun &
\cellitems \item rustc \\
\textbf{sample project management tools} &
\cellitems \item setuptools, \item Poetry, \item Hatch &
\cellitems \item npm, \item Yarn, \item pnpm &
\cellitems \item Cargo
\end{tabular}
\end{table}
We shall compare the numbers of software projects from the chosen ecosystems
that are packaged in system software distributions described in detail
in~\ref{chp:existing-security-tools}. The numbers presented in Table
\ref{tab:ecosystem-packaged-numbers} were estimated based on snapshots of
package collections offered by Debian Bookworm as of \debianTresholdDate{} and
GNU Guix as of \tresholdDateAndCommit{}.
% grep -R node-build-system "$GUIX_CHECKOUT"/gnu/packages | wc -l
% grep -Re '\(pyproject\|python\)-build-system' "$GUIX_CHECKOUT"/gnu/packages | wc -l
%% $ grep -R dh-nodejs ../buildinfos | awk -F _ '{print $1 "_" $2}' | sort | uniq | wc -l
%% 998
%% grep -R dh-cargo ../buildinfos | awk -F _ '{print $1 "_" $2}' | sort | uniq | wc -l
%% 1424
%% $ grep -R dh-python ../buildinfos | awk -F _ '{print $1 "_" $2}' | sort | uniq | wc -l
%% 5312
\begin{table}[htpb]
\caption{Estimated numbers of Debian and GNU Guix packages corresponding to
software from considered ecosystems.} \centering
\label{tab:ecosystem-packaged-numbers}
\footnotesize
\columnsCount{4}
\begin{tabular}{
>{\raggedright\arraybackslash}p{.31\netTableWidth}
>{\raggedright\arraybackslash}p{.23\netTableWidth}
>{\raggedright\arraybackslash}p{.23\netTableWidth}
>{\raggedright\arraybackslash}p{.23\netTableWidth}
}
\rowcolor{gray!40}
&
\textbf{PyPI} &
\textbf{npm} &
\textbf{crates} \\
\textbf{GNU Guix packages} &
$3\,699$ &
$55$ &
$3\,704$ \\
estimated as use counts of which \code{build-system}s in recipes &
\code{pyproject-build-system}, \code{python-build-system} &
\code{node-build-system} &
\code{cargo-build-system} \\
\textbf{Debian packages} &
$5\,312$ &
$998$ &
$1\,424$ \\
estimated as counts of source packages referencing which
debhelper package &
\code{dh-python} &
\code{dh-nodejs} &
\code{dh-cargo}
\end{tabular}
\end{table}
A conclusion arises that for some reason npm packages are less likely to be
packaged when adhering to the rigor of existing software distributions that
utilize hermetic and reproducible builds. We can try to name the main causes
and judge whether the difficulties could be worked around without sacrificing
security.
\section{Dependency tree sizes}
It can be noticed that on avarage, npm projects have more recursive dependencies
than, for example, Python projects~\cite{btao-wot-for-npm}. This means that
packaging an end-user application written in JavaScript\footnote{also referred
to by its official name: ECMAScript} typically requires more labor of bringing
the intermediate packages to the distribution -- an issue that has been talked
about in the GNU Guix community for at least ten
years~\cite{lets-package-jquery}.
Large dependency trees can be partially caused by the JavaScript language
historically having a relatively modest standard library. While such design can
bring some benefits, it might also lead to proliferation of small libraries that
have overlapping functionality. Independent, competing packages with similar
purposes are then more likely to appear together in a single dependency tree.
Creation of many small packages and eager use of dependencies for simple tasks
-- all of which leads to larger dependency trees -- can also be attributed to
the culture of developers working with the npm Registry~\cite{Abdalkareem2020}.
\section{Age of the ecosystem}
The npm tool first appeared in 2010. The PyPI ecosystem is older, with its
repository being launched in 2002. It can therefore be argued that software
from the latter has had more time to be included in Debian and several other
software distributions. However, this is not sufficient to explain the lack of
inclusion of npm packages in GNU Guix, which itself came to existence in 2012.
Additionally, the crates ecosystem, which came to existence in 2014, is younger
than all of the previous repositories. Despite that, software from it has
larger presence in Debian an GNU Guix than software from the npm ecosystem.
\section{Conflicting dependencies}
\label{sec:conflicting-deps}
System software distributions typically only allow a single version of a package
to be installed at any given time. This rule is sometimes relaxed in various
ways. For example, as of \debianTresholdDate{}, Debian Bookworm had distinct
packages named \code{gcc-12} and \code{gcc-11}. Both of them provide the GNU C
Compiler, albeit in different major versions. These packages can be installed
side-by-side. GNU Guix, on the other hand, has facilities to create independent
environments with different sets of packages in each. If multiple versions of
the same package reside in different environments, they do not cause a conflict.
There are also other nuances that provide some degree of flexibility.
Nonetheless, an application that requires multiple versions of a single
dependency is more difficult to include in such software distributions. This is
a relative small issue for, e.g., Python applications. Their runtime does not
support simultaneous loading of multiple versions of the same Python library in
the first place. I.e., if it is possible to install package's dependencies from
PyPI and use that package, it means there are no conflicting dependencies. At
the same time, npm and the Node.js runtime allow multiple versions of the same
library to appear in the dependency tree of a project.
\subsection{Support in npm\&Node.js}
\label{sub:conflicting-deps-in-npm}
Let us consider the dependency tree recorded in \code{package-lock.json} file of
the sigstore project
repository\footnote{\url{https://raw.githubusercontent.com/sigstore/sigstore-js/759e4d9f706aa0bea883267009fa1da8f2705eab/package-lock.json}}.
We shall look at the revision designated by Git commit \code{759e4d9f70} from
Aug 5, 2024. Entries of interest are shown in Listing
\ref{lst:occurances-of-tslib}. A library identified as \code{tslib} appears two
times in the tree. There is a copy of version 2.6.3 and a copy of version
1.14.1. This happened because a dependency, \code{tsyringe}, has a requirement
on a version of \code{tslib} that is at least 1.9.3 but lower than 2.0.0.
Version 1.14.1 present in the tree satisfies this requirement. Another
dependency, \code{pvtsutils}, requires \code{tslib} in version that is at least
2.6.1 but lower than 3.0.0. Several other entries, omitted for clarity, have a
different requirement on \code{tslib}. All these are satisfied by version
2.6.3.
\lstinputlisting[
float=htpb,
language=package-lock-json,
caption=Multiple occurances of \code{tslib} package in a dependency tree.,
label=lst:occurances-of-tslib,
numbers=none
]{occurances-of-tslib.txt}
When this project's code is run and the \code{tsyringe} library tries to load
\code{tslib}, Node.js runtime instantiates version 1.14.1 of \code{tslib}
from \code{tsyringe}'s private subtree. \code{tsyringe} then works with that
instance of \code{tslib}. For all other parts of the project that attempt to
load \code{tslib}, version 2.6.3 is instantiated and used.
\subsection{Effects of Semantic Versioning}
\label{sub:effects-of-semver}
In the npm ecosystem a system called ``Semantic Versioning''
\cite{prestonwerner2013semantic} is widely applied. This system assumes that
software version is given as three numbers -- major, minor, and patch. E.g.,
2.6.3. It also permits optional labels for pre-release and build
metadata. When Semantic Versioning is followed, then a new software release
that breaks backward compatibility with the previous release has its major
version number increased and the other two numbers reset to zero. A release
that adds new functionality without breaking backward compatibility has only its
minor number increased, with patch number reset to zero. And a release that
adds no new functionality -- typically a bugfix release -- has its patch number
increased.
Assume project \code{foo} utilizes a semantically versioned dependency
\code{bar}. The developers could verify that \code{foo}'s code integrates
properly with a particular version of \code{bar}, e.g., version 3.4.5. The
developers would then record a requirement that in the future, either this
version of \code{bar} or a later one -- but without compatibility-breaking
changes -- can be used by \code{foo}. This means only \code{bar} versions
between 3.4.5 and 4.0.0, excluding 4.0.0 itself, would satisfy the requirement.
If \code{bar} then increases its major number in a new release, the developers
of \code{foo} can ensure that its code integrates properly with the newer
\code{bar}. They would then update the requirements in \code{foo} and the next
release of \code{foo} could officially use the 4.x.x series of \code{bar}. It
would, however, still be forbidden from using the hypothetical 5.x.x series that
could bring subsequent compatibility breakages.
In our example from~\ref{sub:conflicting-deps-in-npm}, the libraries
\code{tsyringe} and \code{pvtsutils} both apply this approach to their
dependency, \code{tslib}. As a result, \code{tsyringe} is protected from
possible breaking changes introduced by version 2.0.0 of \code{tslib},
but at the same time it is impossible to satisfy all requirements of the project
with just a single copy of \code{tslib}. In practice, there are sometimes tens
or hundreds such conflicts in a single dependency tree.
The breaking changes that necessitate increasing package's major version number
sometimes concern a part of package's functionality that the specific user does
not rely upon. When project's developers know or suspect that the requirements
specified by certain dependencies could be safely loosened, they can forcibly
override them. Such overrides, supported natively in npm, are used by some when
addressing security vulnerabilities deep in a project's dependency tree. The
same approach could be used to eliminate all dependency conflicts. However,
with many overrides there's a lower chance of avoiding a breakage due to
inter-package compatibility issues.
\section{Difficult bootstrappability}
GNU Guix and Debian are self-contained in the sense that build dependencies of
their packages are also their packages. When packaging a program that requires,
e.g., a C compiler to build, no problems arise -- C compilers are already
present in these system software distributions and one of them can be used as a
build dependency of the new package. However, packaging a program written in a
new programming language requires a compiler or interpreter of that programming
language to be present in the distribution in the first place. The same applies
to other types of build tools, e.g., bundlers that amalgamate many JavaScript
files into a few or a single file.
Packaging a program for such distribution involves first packaging all its build
tools. Making a package buildable with only the tools from the distribution is
sometimes referred to as \textbf{bootstrapping}.
\subsection{Self-depending software}
\label{sub:self-depending-software}
Certain tools exist that depend on themselves to build, making bootstrapping
challenging. Selected examples from the npm ecosystem are presented in Table
\ref{tab:self-depending-packages}. Packages in the table were ranked based on
how many other npm Registry packages specified them as development dependencies
as of \tresholdDate{}. The presented selection is by no means exhaustive, more
highly popular self-depending npm packages might exist.
\begin{table}[htpb]
\caption{npm Registry packages that require themselves to build.}
\label{tab:self-depending-packages}
\centering
\footnotesize
\columnsCount{3}
\begin{tabular}{
>{\raggedright\arraybackslash}p{.13\netTableWidth}
>{\raggedright\arraybackslash}p{.27\netTableWidth}
>{\raggedright\arraybackslash}p{.6\netTableWidth}
}
\rowcolor{gray!40}
\textbf{name} &
\textbf{popularity ranking} &
\textbf{notes} \\
\code{typescript} &
$1$ ($473\,235$ dependees) &
the original implementation of TypeScript programming language \\
\code{@babel/core} &
$10$ ($138\,704$ dependees) &
part of a JavaScript compiler, requring itself indirectly through
dependencies that themselves build with \code{@babel/core} \\
\code{rollup} &
$26$ ($95\,965$ dependees) &
a bundler \\
\code{gulp} &
$40$ ($61\,077$ dependees) &
a build system, requiring itself through its runtime dependency
\code{gulp-cli} \\
\code{sucrase} &
$1\,793$ ($528$ dependees) &
an alternative to Babel, used as a proof of concept for bootstrapping a GNU
Guix package
\end{tabular}
\end{table}
In GNU Guix, the preferred approach to packaging a self-depending tool is making
it bootstrappable~\cite{courtès2022buildingsecuresoftwaresupply}. This can
happen by packaging a chain of historical versions of the tool, where each can
be built with the nearest older packaged one, down to an early version that did
not have a self-dependency. Sometimes it is possible to eliminate or shorten
such ``bootstrap chain'', for example by replacing a complex build tool with
scripts or by using a bootstrappable drop-in replacement to some tool. The
latter was an approach used to package the official, self-hosting implementation
of the Rust programming language for GNU Guix in 2018. There, an unofficial
Rust compiler, written in C++, was used to compile an official Rust release from
July 2017~\cite{bootstraping-rust}.
Bootstrapping helps prevent the ``Trusting Trust'' attack demonstrated by Ken
Thompson in 1984, but as of today there is little evidence of such attack type
ever being used by threat actors. In some cases software distributions under
consideration make exceptions and allow a non-bootstrappable program prebuilt by
another party to be made into a distribution package. For example, the set of
OCaml and Haskell compilers in GNU Guix depends on such third party binaries
that cannot be rebuilt from any package recipe in the distribution.
In 2022 a proof of concept GNU Guix bootstrap of \code{sucrase}, a
self-depending build tool from the npm ecosystem, was
done~\cite{re-bringing-npm-to-guix}.
\subsection{Recursive dependency closure}
By package's recursive development dependency closure we mean a set containing
all its declared runtime dependencies and development dependencies, their
runtime dependencies and development dependencies, etc. In other words, the
closure is the minimal set that contains the dependencies of its every member
and also of the package for which the closure is being computed. The size of
package's recursive dependency closure can illustrate the bootstrapping
challenge complexity. An attempt to compute such closure was made for npm
package \code{typescript} as part of this work. npm Registry metadata limited
to package releases from before \tresholdDate{} was used. For simplicity,
version constraints were disregarded and packages' all historical dependencies
were considered. The result was a $60\,843$-elements big set of package names,
with additional $2\,433$ referenced names that do not exists in the Registry.
These were largely the results of mistakes and possibly private/unpublished
packages. Of course, non-crucial tools like linters tend to be declared
developments dependencies and the closure of truly necessary dependencies would
be much smaller, as also reported in~\ref{sec:typical-dep-tree-sizes}.
Nonetheless, this example shows how difficult it is to reason about what is
needed for bootstrapping tasks.
\section{Inconvenience of system software distributions}
\label{sec:inconvenience-of-distros}
Despite looser security practices and more frequent reports of malicious
packages in repositories like the npm Registry
\cite{malicious-npm-techtarget-nichols,malicious-npm-infosec-muncaster,malicious-npm-cybernews-naprys,malicious-npm-bleep-toulas,malicious-npm-hacker-news-ravie},
many developers still prefer to work with them rather than with system software
distributions. Packages in the latter are adjusted to work with and inside
their distributions and are typically not compatible with the usual workflow of
developers of, e.g., npm projects. For example, it could be unstraightforward
to use npm libraries from Debian for producing distribution files of a mobile
application. Another deterrent is the delay with which newer releases of
packages reach system software distributions.
This limited interest in availability of software from certain ecosystems in
distributions like Debian and GNU Guix also leads to decreased incentive for
authors of these distributions to work on it.
\chapter{Overview of the npm ecosystem}
\label{chp:npm-ecosystem-overview}
Software from the npm ecosystem was found to be more challenging to be made into
system software distribution packages. To provide deeper insight into this
problem, this chapter provides more information about this ecosystem, with focus
on dependency relations between npm packages.
npm Registry -- the software repository around which the npm ecosystem is
centered -- was created as a distribution channel for JavaScript libraries,
frameworks, and applications using Node.js runtime. It was targeted towards
server-side developers. The platform allows the general public to register
accounts and publish software packages. Throughout the years, the npm Registry
also became home to client-side JavaScript, i.e., software to be executed in web
browsers. The repository is nowadays also used by related programming
languages, notably TypeScript. As of \tresholdDate{}, the repository was
serving over $3.5$ million published packages, many of which come in multiple
versions.
\section{Recognized dependency types}
Projects using npm can use a structured format to list their dependencies, i.e.,
the npm packages they use. Four types of dependencies can be specified in
package's metadata kept in a file named \code{package.json} in project's source
directory. These types are described in Table~\ref{tab:npm-dep-types}.
Throughout the rest of this work, the opposite of a dependency shall be called a
\textbf{dependee}.
\begin{table}[htpb]
\caption{Dependency types recognized by npm.}
\label{tab:npm-dep-types}
\centering
\footnotesize
\columnsCount{2}
\begin{tabular}{
>{\raggedright\arraybackslash}p{.3\netTableWidth}
>{\raggedright\arraybackslash}p{.7\netTableWidth}
}
\rowcolor{gray!40}
\textbf{Metadata key} &
\textbf{Meaning} \\
\code{dependencies} &
Packages needed at runtime. \\
\code{devDependencies} &
Packages needed or useful for development, often minifiers/bundlers, test
frameworks, linters, and version control integration tools. \\
\code{optionalDependencies} &
Similar to \code{dependencies} but only needed for some additional
functionality. npm supports installing a package without its optional
dependencies, but by default it does install them. \\
\code{peerDependencies} &
Used to specify compatible versions of tools for which the dependee is a
plugin.
\end{tabular}
\end{table}
\section{Statistical analysis of the npm ecosystem}
To determine which projects using npm Registry are the most popular among
developers, the dependency relations between packages were counted and analyzed.
First, the metadata of all published packages in JSON format was downloaded.
Download took place on the days following \tresholdDate{}. The metadata was
processed to only include information about releases made after \tresholdDate{},
yielding $3\,519\,767$ package entries. Curl program was used to make requests
to Registry's CouchDB view at \url{https://replicate.npmjs.com/_all_docs}. It
is worth noting that this API endpoint's functionality has since changed and
other means would be necessary to download the entire Registry metadata again in
the future.
For the purpose of rankings discussed next, the dependees being multiple
versions of a single package were counted as one. Similiarly, version
constraints in dependency specifications were ignored.
\subsection{The most popular dependencies -- changes over five years}
\label{sub:npm-changes-5-years}
One of several metrics of package's popularity is its number of public
dependees. Up to 2019 such a ranking of $1\,000$ packages most often specified
as others' dependencies used to be published by Andrei
Kashcha~\cite{anvaka-rank-gist}. A similar list computed from newer data for
the purpose of this work was used to check how much the set of the most popular
packages changed between August 2019 and April 2025. The goal was to find out
how many of the previously popular projects keep to be chosen by developers and
how many stopped being actively used, perhaps becoming legacy software. The
overlap between the rankings is visualised in
Figure~\ref{fig:common-2019-2025-percent}. For each natural $n$ in the range
$[1, 1000]$, $n$ most popular dependencies from both rankings were selected.
The overlap of selected packages from first and second ranking was computed and
plotted with the values of $n$ on the X axis of the figure.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{common_2019_2025_percent.svg}
\caption{Overlap of the most popular npm dependencies from 2019 and 2025.}
\label{fig:common-2019-2025-percent}
\end{figure}
The ``winners'' in 2019 and 2025 were \code{lodash} and \code{react} with
$69\,147$ and $263\,038$ dependees, repsectively. It can be seen that about
$150$ most depended packages form a relatively stable forefront, with further
part of the ranking having changed more over five years. Nevertheless, it is
worth noting that certain packages with no new releases for several years still
rank relatively high in 2025. Examples are \code{lodash}, \code{request}, and
\code{q} ranking third, $17$th, and $157$th, respectively.
As a conclusion, if certain software is intended to be used for more than a few
years, dependencies for it must be considered more carefully when they are not
from among the \givemeatilde150 most popular ones. Otherwise, the risk of
project's direct dependency becoming legacy software grows. However, often
other characteristics of a package will determine whether it should be
considered reliable. Ultimately, the matter of who maintains a package and how
it could help the project are more relevant than a ranking position.
\subsection{The most popular dependencies -- popularity tresholds}
\label{sub:runtime-deps-popularity-tresholds}
The numbers of dependees corresponding to ranking positions can be used to infer
some qualities of the ecosystem. This correspondence is presented in
Figure~\ref{fig:dependee-counts}.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{dependee_counts.svg}
\caption{Number of packages using the most popular dependencies.}
\label{fig:dependee-counts}
\end{figure}
In 2019, the $1000$th most popular dependency package in the npm Registry had
$346$ dependees. By April 2025, the $1000$th package in the ranking had already
$4\,771$ dependees. This reflects the growth of the entire ecosystem, whose
package repository had about one million packages in July 2019 and about $3.5$
million packages in April 2025. However, this would by itself only explain a
rise in dependee counts by about a ratio of $3.5$. The aforementioned increase
from $346$ to $4\,771$ dependees is over four times greater. This needs to be
attributed to growing projects' complexity, as there is a tendency to use more
dependencies. A plausible additional explanation is higher overlap of
functionalities between packages, i.e., situations occur where multiple popular
libraries exist for a single task.
\section{The most popular development dependencies}
\label{chp:most-popular-dev-deps}
In the context of supply chain security, the development dependencies are as
important to research as the runtime dependencies. A popularity ranking similar
to the previous one was compiled for packages occuring the most in the
\code{devDependencies} collections of others. An analogous correspondence of
ranking position to development dependee count is presented in
Figure~\ref{fig:dev-dependee-counts}. No development dependencies ranking from
2019 was found that could be used for comparison. Instead, the runtime
dependencies plot from Figure \ref{fig:dependee-counts} was re-included for
easier reference.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{dev_dependee_counts.svg}
\caption{Number of packages using the most popular development dependencies.}
\label{fig:dev-dependee-counts}
\end{figure}
The first position belongs to \code{typescript} with $840\,161$ development
dependees. A treshold of $2\,185$ development dependees needed to be reached by
a package to be included in the ranking. The curve for development dependencies
is steeper, meaning there is a clearer forefront. This in turn indicates that
the functionality overlap mentioned in
\ref{sub:runtime-deps-popularity-tresholds} is possibly a smaller problem in
this case.
\section{Overlap of the most popular runtime and development dependencies}
\label{sec:overlap-of-runtime-and-dev-deps}
It is possible for a popular development dependency to also be specified as a
runtime dependency by some packages. Realizing how often this happens can help
judge whether certain kinds of issues are likely to occur in the ecosystem. The
overlap of runtime and development dependencies is visualized in
Figure~\ref{fig:common-nondev-dev-percent}, using the same approach as for the
overlap in Figure \ref{fig:common-2019-2025-percent} discussed in
\ref{sub:npm-changes-5-years}.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{common_nondev_dev_percent.svg}
\caption{Overlap of the most popular npm runtime and development dependencies in
2025.}
\label{fig:common-nondev-dev-percent}
\end{figure}
Since packages listed as \code{dependencies} are often libraries or
frameworks and those listed as \code{devDependensies} are commonly
applications, one could expect a smaller overlap than that of about 15-30\%
which was found. A possible explanation is that unlisting a package from
\code{devDependencies} add instead including it among
\code{dependencies} creates no major change for project developers. A
command like \code{npm install} shall still resolve that dependency and
include it in the environment it creates. It is therefore possible that a
non-negligible number of dependencies is incorrectly categorized by the
dependees.
It used to be a known fact that among packages listed as \code{devDependencies}
there are many which are not needed to merely rebuild a project. These could be
automatic code formatters, tools responsible for integration with version
control, etc.\ and they could be eliminated from automated builds to make them
lighter on resources and to decrease the attack surface. Based on these results
it is reasonable to expect that the similar holds for runtime dependencies.
This provides a justification for experiments aimed at eliminating the
extraneous dependencies without breaking the functionality of packages.
\chapter{Possible paradigms for hermeticity and reproducibility}
Certain popular software technologies -- with npm being one of them -- prove
difficult to combine with existing reproducibility-focused workflows. Possible
causes of this were discussed in~\ref{chp:applicability-of-workflows}. The
package creation workflows of -- largely reproducible -- system software
distributions Debian and GNU Guix were explained in
\ref{sub:how-debian-package-is-made} and~\ref{sub:how-gnu-guix-package-is-made},
respectively. An explanation of the npm ecosystem followed in
\ref{chp:npm-ecosystem-overview}.
With all the above being considered, the ability to handle software with
numerous dependencies -- which can have complex relatonships -- appears relevant
to the goal of rebuilding parts of the npm ecosystem hermetically and
reproducibly. Based on the knowledge gathered, possible approaches to
hermeticity and reproducibility in the context of dependency resolution shall be
critically analyzed. They shall be classified as distinct paradigms. The
introduced paradigms shall be discussed in the context of security and their
applicability to the build process of npm pacakges.
Paradigms 0 through 2 represent existing approaches. Paradigm 3 is an
intermediate one that leads to 4, which is a generalization of the former.
Paradigms 3 and 4 are an innovation originating from this work. They are meant
to optimize the way build inputs are determined and also ensure that no
unnecessary single points of failure are created which would not be secured
through verified reproducibility. The new paradigms are suggested as bases for
hypothetical new software packaging workflows that would make hermeticity and
reproducibility easier to achieve with software from, among others, the npm
ecosystem.
\section{Paradigm 0 -- lack of actual reproducibility}
\label{sec:paradigm-0}
If one is to build an npm package in the most basic way, with use of commands
like \code{npm install} and without a pre-computed dependency tree, then network
connectivity is necessary. Without it, the npm tool cannot download packages
metadata from its repository, the npm Registry. But if network access is
allowed, then the build -- and therefore its result -- might depend on
downloaded code and data other than dependencies' metadata. Some commonly used
npm packages require additional connections to function. For example, the
\code{playwright-webkit} library, upon installation by npm, downloads
executables from a third party server. That library is an intermediate test
dependency of a popular web library, JQuery, used by about 74\% of the most
popular websites~\cite{w3techs-javascript-library}.
Author of an npm package can assign so-called \textbf{distribution tags} to its
specific versions. The tag can be though of as a string label that points to a
package version. Tags can be used by dependees as an alternative way of
specifying the depended version of the package. Some of the commonly used tag
names are \code{next}, \code{beta}, and \code{latest}. When the developer
publishes a new package version, the npm tool by default automatically assigns
the \code{latest} tag to that version.
The build process of an npm project relies on downloaded metadata of packages.
As a result, if a dependency author publishes its new version or alters the
distribution tags, it might cause later rebuilds of the package to use a
different set of inputs. The final result can be different, so it is not
reproducible. Additionally, the repository constitutes a single point of
failure because compromising the repository allows altering the served metadata
of package versions. The compromised repository could, for example, spoof
package's distribution tags or hide the existence of certain versions of a
package, thus allowing only vulnerable versions to be used.
With files coming from a third party server, we have even less guarantee that
they were not maliciously tampered with. A library that downloads such files
during package build could verify them. For example, its authors could make the
library contain cryptographic hashes of the required external files. The
library could then check that every downloaded file has a matching hash.
Unfortunately, we have no mechanisms to mandate that this kind of verification
takes place in cases like that of \code{playwright-webkit}. This means ad-hoc
file downloads are a bad security practice. They would need to be eliminated or
restricted for reproducibility to be leveraged.
Despite the above, reproducibility tests of npm packages are actually attempted,
with one example being Pronnoy Goswami's research
\cite{goswami-reproducibility}. It has to be noted that the results of such
tests are likely to be unstable, yielding different results if repeated at a
later date.
\section{Paradigm 1 -- inputs determined by human-maintained references}
One of the possible methods of determining the set of build inputs is used by
GNU Guix. Its package recipes contain references to dependency packages that
have their versions predetermined. As a result, questions like ``Should
\code{foo} use its dependency \code{bar} in version 2.4.5 or 3.0.1?'' are
already answered. An update to a package definition results in the updated
package being used everywhere that particular definition was referenced. The
update takes form of a commit or commit series in the Git VCS and is subject to
review by co-authors of the distribution.
If we fix a GNU Guix revision to be used, then in a package build -- which is
hermetic by design -- all inputs are unambigiously determined. No repository of
metadata can open the user to the risk of using incorrect dependency versions.
In other words: the threat on the part of improperly defined dependency versions
is of the same nature as that on the part of improperly written code. And -- as
users of any kind of software -- we are deemed to accept threats of this nature.
Maintenance of this kind of system is, of course, more labor-intensive. Every
alteration of a package recipe -- also including software's version updates --
is an update to GNU Guix' Git repository. Such update involves labor of
distribution maintainers, similarly to Debian's case. A sample list of $26$
consecutive commits to GNU Guix' repository -- with $15$ package updates among
them -- is presented in Listing~\ref{lst:guix-package-update-commits}. The
changes in the list were made by multiple contributors during an hour between
12:00 and 13:00 on April 11, 2025. The changes are listed oldest to newets.
Details of the newest one are additionally shown. A non-negligible amount of
work is clearly needed to handle many changes manually. The great number of
small changes might therefore lead to a yet unverified assumption that too big
effort is required of distribution maintainers. If true, this could hamper the
growth of the software collection available through GNU Guix.
\lstinputlisting[
float=htpb,
language=guix-commit,
caption={List of consecutive changes committed to GNU Guix, with contents of
the bottommost one included for reference.},
label=lst:guix-package-update-commits,
numbers=none
]{guix-package-update-commits.txt}
In addition, many package managers following other paradigms can make use of
permitted dependency version ranges declared by packages. This way npm, APT,
and others can automatically avoid using incompatible dependency versions.
However, Paradigm 1 does not allow such optimization to be employed.
It is worth highlighting that in GNU Guix the URLs and hashes that comprise
identification data of program sources are maintained together with package
recipes, as can be seen in Listing~\ref{lst:guix-package-update-commits}. As
explained, this approach might have additional consequences in the amount of
distribution maintainers' labor. Nonetheless, it can also positively or
negatively affect the chances of malicious sources being referenced in a recipe.
This is an important supply chain issue to recognize, but it is independent from
the concept of paradigms introduced in this chapter.
\section{Paradigm 2 -- reproducibility not applied to dependency resolution}
The problem of the dependency resolution process being unreproducible was
explained in~\ref{sec:paradigm-0}. In this context, the actual package build
can be partitioned into several distinct steps, for example
\begin{enumerate}
\item dependency resolution,
\item dependency installation,
\item code transformation/generation,
\item automated tests, and
\item installation/packing.
\end{enumerate}
Steps 1 and 2 are sometimes performed together, for example as part of a single
command invocation. However, in case of some package managers -- including npm
-- the set of resolved dependencies with their versions can also be recorded for
later reuse. It is done with so-called \textbf{lockfile} -- a file that project
developers can add to a VCS and which allows dependency installation to be
repeated without re-downloading metadata nor re-running the resolution
algorithm. In npm projects this file is saved as \code{package-lock.json} or
\code{npm-shrinkwrap.json}.
With a precomputed \code{package-lock.json} we can therefore download the
dependencies and use them as inputs of the hermetized build, narrowed to steps
2-5. Upstream software's original build procedures sporadically expect network
access during these steps. The build process of the aforementioned JQuery is
one of those few cases where this occurs. Such problems would need to be
corrected manually, in package recipes of a hypothetical distribution applying
Paradigm 2 to a broader population of npm packages. A typical solution in,
e.g., Debian is a patch that eliminates such access attempt or replaces it with
a reference to a local, formally-approved input.
If npm project authors fail to provide an appropriate lockfile -- which can
happen -- it could be generated by one of the parties that rebuild the software.
Step 1 would then need to be performed unhermetically, with network access. The
obtained \code{package-lock.json} would then be treated as additional build
metadata, distributed to the other parties. When a build were to be repeated to
verify the reproducibiliy of the result or for other purposes, presence of this
metadata would be required.
The benefit of Paradigm 2 is that one can proceed in achieving reproducibility
of most of the build process and further leverage it. In fact, comments in the
source code of JQuery indicate that its developers -- to some extent and with
disregard for possible changes in files being downloaded during the build
process -- did actually work on making JQuery's build process deterministic when
the \code{package-lock.json} is used.
The main disadvantage of Paradigm 2 is that dependency resolution is still not
secured by hermeticity nor reproducibility. Even when changes to project's
\code{package-lock.json} take the form of version control system commits, these
are unlikely to be reviewed as carefully as ordinary software code changes.
Dependency trees can be complex. \code{package-lock.json} files counting over
$1000$ entries are common. As a result, the shape of a particular resolved
dependency tree is difficult to explain without additional tools.
The described approach requires generalization to building a project that uses
multiple repositories, e.g., npm Registry + Python Package Index + Rust Package
Registry. That is because multiple dependency trees from multiple software
ecosystems are involved. Theoretically, even in terms of a single ecosystem and
a single repository, we might need to resolve multiple sets of dependencies in
step 1. In effect, an actual collection of lockfiles would need to be treated
as the aforementioned additional build metadata.
\subsection{Debian implementation}
Interestingly, a variant of Paradigm 2 can be found in Debian, which is
considered one of the most reproducible software distributions. That is because
the package recipe shared as \code{debian.tar.xz} file contains the names of
direct build dependencies but not necessarily their precise versions nor the
indirect dependency names. It is actually the \code{.buildinfo} files where the
published packages' build environments metadata can be found. Much of this
metadata is determined by the dependency resolution process, as performed by
Debian's APT tool during the initial Debian package build.
Although this does formally fall into the scope of Paradigm 2, Debian packagers'
perspective is still similar to that of Paradigm 1 users. That is because -- as
explained in~\ref{sec:conflicting-deps} -- a single Debian release typically
only advertises a single version of a given package at any point in time.
Unless multiple Debian releases are mixed together, this makes the input
metadata of APT's dependency resolution process flat. This, in turn, makes
packagers ultimately responsible for ensuring version compatibility between
packages in this flat space.
\section{Paradigm 3 -- deterministic dependency resolution inputs ensured}
\label{sec:paradigm-3}
For our dependency trees from Paradigm 2's step 1 to be secured through
reproducibility, we need to be able to repeat the dependency resolution step
using the same data about candidate dependency packages. Neither
\code{.buildinfo} nor \code{package-lock.json} files preserve all metadata
actually consulted by the resolution algorithm. They lack information about
packages that were considered but rejected as final dependency tree members. As
such, full dependency resolution cannot be performed based on just these files'
contents. It can be argued that the risks this causes for Debian are small
because the general public cannot create new packages that could then be
immediately used as dependencies. Here, one of the most likely dependency
resolution attack scenarios involves supplying the build with an outdated,
faulty compiler package already present in the distribution. One theoretical
attack utilizing a compiler bug was described
in~\cite{deniable-backdoors-compiler-bugs}. In contrast, manipulation of
\code{package-lock.json} in an npm package build can more easily lead to an
attacker-published package being installed in the build environment.
In case of npm projects, one of the simplest solutions would be pointing the npm
tool to a local mock of a repository server, speaking the HTTP protocol. The
mock would function as a proxy that downloads required packages' metadata from
the original npm Registry server, alters it and returns it as responses to the
npm tool's requests. Each response -- containing the metadata of all versions
of a single npm package -- would be filtered not to include the versions of
packages that were published after a chosen time treshold. The treshold could
be, e.g., the release date of the project version being built. In repeated
build attempts, the relevant metadata served by mocked registry ought not to
change. Corner cases shall occur, in form of dependencies being removed from
the official registry due to copyright claims or in form of projects' dependence
on particular developer-alterable distribution tags of npm packages. These
problems should be rare enough to be fixable manually or with reasonable
defaults. For example, a mock \code{latest} tag could be attached to the newest
version of each npm package whose metadata is served.
This approach does not completely eliminate the threat of the dependency
resolution process being maliciously influenced. In particular, the packages'
metadata could be maliciously modified even earlier, for example as a result of
the official registry's infrastructure being compromised. However, compared to
Paradigm 2, the number of moments when malicious modifications could occur is
decreased. Similarly, the scope of what could be modified is more limited. To
decrease the changes of the hypothetized attack on the registry being
successful, additional means of detection and mitigation could be employed. For
example, trusted third parties can serve as ``canaries'', publishing
cryptographically signed information about what package metadata was being
served by the repository as of given date. The initial builder can also record
the resolution metadata and make it available to rebuilders, effectively acting
as one of the suggested canaries. The holy grail of avoiding a single point of
failure -- one in the form of a centralized registry -- would be deriving the
resolution metadata of packages from those packages themselves once they are
also rebuilt locally. This would present a bootstrapping challenge that -- when
solved -- would open the way to dependency resolution without major reliance on
any centralized service.
Regardless of the employed approach to securing the dependency resolution
inputs, the actual concept of Paradigm 3 is to make the inputs plausibly
deterministic and then repeat the dependency resolution process upon every
repetition of a given package build. The remaining steps of the build process
are performed analogously to those in Paradigm~2. The issue of generalization
to projects utilizing multiple repositories is also analogous to that in
Paradigm~2.
\section{Paradigm 4 -- hermeticity relaxed and deterministic dynamic inputs allowed}
One can notice that in paradigms 2 and 3 the first step, dependency resolution,
is treated different from the subsequent ones. The result of step 1 is a
collection of one or more lockfiles that identify dependencies' files, e.g.,
through names and versions or URLs and hashes. A tool that implements a given
paradigm would need to -- between steps 1 and 2 -- prepare an appropriate
isolated environment for package build, for example a Linux container.
Lockfile-identified dependencies would need to be exposed inside.
In Paradigm 3, the initial download of packages metadata can happen through a
locally-run mock of a repository server. I.e., the isolated dependency
resolution process has a service perform possibly hermeticity-violating actions
on its behalf. Yet, care is taken to make the results of those actions
deterministic. Paradigm 4 extends this approach to all steps of the build. The
installation step, knowing project's recursive dependencies identified by the
lockfiles from step 1, could have the service supply the dependencies' files
into the otherwise isolated build environment. There is no more need to provide
separate isolated environments to two different parts of the build process --
step 1 and the chain of remaining steps. As long as the hermeticity-violating
actions performed by the service on build's behalf are deterministic, this
should not make build results less reproducible. The process can be thought of
as \textbf{eventually-hermetic}, bacause repeated builds are likely to request
the exact same actions, requiring the same external data, which could be cached
and reused, making subsequent runs network-independent. At the same time, this
approach \textbf{removes the need of having all build inputs identified in
advance}, simplifying the entire build process.
Let us provide another example of an action that could be deterministically
carried out on behalf of the build -- checking out of a Git repository revision.
Under Paradigm 4 this could happen through the hermeticity-violating service,
making the repository a \textbf{build input determined dynamically}. If the
checkout operation uses a repository URL and, e.g., a Git tag\footnote{unrelated
to npm package's distribution tag and not to be confused with it}, it is by
itself not deterministic -- result can vary in time, for example due to tags
being changed in the upstream repository. In this case, additional means --
like those already mentioned -- would be needed to ensure the determinism of the
checkout action. However, no such extra measures are necessary if the checkout
operation uses a commit hash made with an algorithm deemed cryptographically
secure. Preimage attack resistance is of practical relevance, making even SHA-1
applicable as of 2025.
This approach makes the logic of an eventually-hermetic package build more
straighforward. If, for example, step 3 required an extra resource or tool, in
paradigms 1-3 that requisite would need to be identified beforehand. Under
Paradigm 4 this is not necessary.
\subsection{Security-oriented justification}
How secure would the Paradigm 4 be? Its security relies on the viability of
employed means of ensuring the determinism of dynamic inputs. A GNU Guix-like
approach of maintaining the cryptographic hashes of all downloadable resources
in a VCS is possible. While the collection of resources still needs to be
identified in advance of any build, there is no more need to record exactly
which ones are needed for which particular package build -- by itself a huge
simplification. This makes Paradigm 4 no worse than -- seemingly the most
secure -- Paradigm 1, as implemented in GNU Guix.
However, the concept of paradigms -- as introduced by this work -- is not
strictly dependent on the way of ensuring the integrity and determinism of
software sources and of other build inputs. The approach of keeping hashes of
packages' sources embedded in code kept in a VCS can be criticized. In theory,
changes to the version-controlled recipes code -- with input resources' hashes
-- are subject to review. However, despite the positive security aspects of
human-conducted code reviews, such system makes it easy for reviewers to lose
vigilance -- especially when facing a ``flood'' of package recipe updates, as
shown in Listing \ref{lst:guix-package-update-commits}. Some could argue that
it would be beneficial to completely replace the version-controlled hashes of
sources with a network of canaries that record the tagged revisions found in VCS
repositories and the contents of software's published release files. This
aproach is applicable to Paradigms 4, 3, and 1 alike. It simply happens not to
be employed by GNU Guix as of 2025.
\chapter{Automated package builds experiment}
\label{chp:experiment}
The previous chapters of this work has lead to the following hypotheses and
questions.
%% \let\labelenumiOld\labelenumi
%% \newdimen\labelwidthOriginal
%% \labelwidthOriginal=\labelwidth
\newcounter{hyQuCounter}
\newcommand{\hyQuItem}[1]{%
\stepcounter{hyQuCounter}%
\item[#1 \thehyQuCounter{}.]%
}
\newcommand{\hypothesis}{\hyQuItem{HYPOTHESIS}}
\newcommand{\question}{\hyQuItem{QUESTION}}
\begin{description}
\hypothesis{} The dependency tree sizes of npm packages and acceptance of
conflicting dependencies by the platform appear to be the major sources of
difficulty in packaging the npm ecosystem in reproducibility-focused
distributions. Is this truly the main factor?
\hypothesis{} Re-generation of npm lockfiles -- an operation necessary for the
security improvement offered by proposed paradigms 3 and 4 over Paradigm 2 --
is expected to rarely cause npm package build failures which would not occur
with developer-supplied lockfiles. Are such failures indeed uncommon?
\hypothesis{} As speculated in \ref{sec:overlap-of-runtime-and-dev-deps}, both
direct and indirect dependencies of npm projects are often unnecessary. Is
this indeed the case?
\question{} What are the typical sizes of dependency trees needed to build npm
projects and how much can these trees be typically shrinked?
\question{} How often do dependency conflicts actually occur in npm dependency
trees and how often -- or to what extent -- can they usually be forcibly
eliminated without causing breakage?
\question{} Are forced removals of npm project's dependencies and forced
elimination of dependency conflicts likely to cause non-obvious breakages that
only become apparent when seemingly successfully-built package turns out to be
disfunctional or nonfunctional? If so, how best to avoid them?
\hypothesis{} npm projects' dependencies are seldom specified by distribution
tags and removal of distribution tags from npm dependency resolution metadata,
with automatic addition of a mock \code{latest} tag as mentioned
in~\ref{sec:paradigm-3}, is expected to cause few dependency resolution
failures. Is this a valid assumption?
\question{} Can we deliver a prototype that performs npm project's dependency
resolution as proposed in paradigms 3 and 4?
\end{description}
To verify and answer these, an experiment was conducted which involved automated
build attempts of top npm projects, selected by their position in the npm
Registry package rankings. The selected set consisted of projects belonging to
the first $200$ of either the most popular \code{dependencies} or
\code{devDependencies} as of \tresholdDate{}. Due to some overlap between the
rankings, the actual size of the set was \allSelectedCount{}. The build
procedure, described in the following subsection, was designed with the help of
a trial-and-error approach.
\section{Method and environment}
The experiment was conducted on an x86\_64 machine. For details, see
Listing~\ref{lst:cpu-info}. All operations were performed under version
5.15.0 of the Linux kernel. All filesystem operations were backed by an
ext4 filesystem. No effort was made to employ means like disorderfs, described
in~\cite{DBLP:journals/corr/abs-2104-06020}, because this work is not concerned
with eliminating the traditional sources of nondeterminism.
\lstinputlisting[
float=htpb,
caption={Details of the processor used during the experiment, as reported by
cpuinfo utility.},
label=lst:cpu-info
]{cpu-info.txt}
The diagram in Figure \ref{fig:experiment-activity} describes the flow of
activities during testing of a single npm project. In the diagram, start and
end are denoted by a filled circle and a circle with a white ring inside,
respectively. Flow branches are represented by hexagons and merges -- by
rhombuses. The particular operations present in the diagram are described
further below.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{experiment-activity.svg}
\caption{Activity diagram describing the experiment as performed on each
tested npm project.}
\label{fig:experiment-activity}
\end{figure}
\subsection{Containerized environment creation}
For each tested project, the version to build was first selected as its highest
non-pre-release package version published before \tresholdDate{}. Versions'
publishing dates that were consulted were part of packages' metadata downloaded
from the npm Registry. For the selected version, the relevant Git repository
URL and -- where possible -- release's Git commit hash were extracted from the
available metadata. The URL was sometimes present with a \code{git+} or
\code{git:} prefix, which had to be dropped. The repository at learned URL
was then cloned to a local directory, with submodules included through the use
of Git's \code{--recurse-submodules} option.
Upon successful retrieval of source repository contents, a semi-isolated
environment, based on Linux containers, was created. Upon creation, the
environment only had access to a minimal collection of software. It comprised
\begin{itemize}
\item
Node.js runtime including bundled npm application,
\item
Git version control tool,
\item
GNU Bash shell, which served as the POSIX-compliant shell used by \code{exec}
function of Node.js,
\item
GNU Coreutils,
\item
GNU which, invoked by experiment's code,
\item
GNU Guile and several Guile libraries, being the driver for the experiment's
code, and
\item
dependencies of the above, e.g., a C library.
\end{itemize}
The environment was created as a container shell managed by GNU Guix. The
version of GNU Guix used was built from Git revision \tresholdGuixCommit{}, the
last one before \tresholdDate{}. It featured Node.js runtime in version
22.14.0, npm in version 10.9.2, and Git in version 2.49.0.
Inside the environment, the applications listed above were available through the
\code{PATH} variable and also symlinked under \code{/bin} directory through the
use of \code{--emulate-fhs} option of \code{guix shell}. The environment had no
direct access to outside network, allowing us to state that experiment's results
reflect the behavior of a hermetic build process. Network isolation also helped
make sure that no dependency was installed ``on the side'', without being
recorded in project's lockfile. The environment was also isolated
filsystem-wise, with specially prepared directories shared between the
environment and the host. They were shared read-write or read-only, according
to needs. Shared directories allowed container's guest to
\begin{enumerate}
\item
access the code used to drive the experiment,
\item
access npm project's cloned repository,
\item
request npm packages' metadata and files from the host through named fifos,
\item
receive them as files, and
\item
persist lockfiles and final package files generated during build, for later
inspection.
\end{enumerate}
\subsection{Source code checkout preparation}
Inside the just-created environment, a checkout to npm project's appropriate
revision was attempted in the following ways.
\begin{enumerate}
\item
By switching to the commit hash previously extracted from the package
metadata.
\item
By switching to a Git tag identical -- as a string -- to the version being
built.
\item
By switching to a Git tag identical to the version being built, prefixed with
letter ``v''. E.g., for a project version 3.2.2 a switch to Git tag
\code{v3.2.2} would be attempted.
\end{enumerate}
This sequence of tries was chosen based on findings from initial manual
experiments and also on prior knowledge of common developer practices. In
particular, it was found that a Git commit hash is not always advertised for
a given npm package version. When it is, it sometimes corresponds to a revision
that was never pushed to project's public repository. This appears to be most
often caused by an automated release publishing software that makes a local
commit as part of its operation. It was decided that in both cases -- of the
unknown and nonexistent commit hash -- it is best to fall back to probable Git
tags.
If directories named \code{node\_modules} or \code{dist} existed in a
successfully checked-out source repository, they were deleted before the actual
build attempt. These directories are used to store npm project's installed
dependencies and generated files, respectively. Although they are sometimes
checked into version control, they are not sources per se and a hygienic npm
project build should be performed without them.
It is worth noting that every build was conducted inside a full git repository
checkout, with access to the \code{.git} directory containing project's history.
This is unlike the practice of GNU Guix, Debian, and many other distributions
where build inputs typically do not include any version control metadata. The
decision was made based on the following considerations.
\begin{enumerate}
\item
Build procedures most often rely on version control metadata for side tasks
like generation of software authors list. These tasks are not highly relevant
to our stated questions, but their failures could decrease the number of
successful package builds that we seek to further analyze.
\item
In actual distribution software packaging, the build process' reliance on
version control metadata is considered easy to solve compared to the issues
of dependencies.
\item
While availability of version control metadata could theoretically ease
smuggling of backdoor code in XZ-style attacks, it would be hardly practical
-- the backdoor would need to be somehow retrieved from version control
history and invoked, in a hard-to-notice way. Building with full version
control metadata is therefore a secure enough approach to be suggested for
adoption by distributions.
\end{enumerate}
\subsection{Dependency resolution in a network-isolated environment}
Dependency resolution was performed with the help of a dummy
\code{npm uninstall} command, as shown in Listing~\ref{lst:npm-uninstall}.
The options used made npm
\begin{itemize}
\item
refrain from attempting network requests unrelated to the actual dependency
resolution,
\item
refrain from actually installing the resolved dependencies or running their
hooks,
\item
update project's lockfile to the current format if an older one was
encountered, and
\item
make requests to a local mock of npm's repository.
\end{itemize}
The command either created the \code{package-lock.json} file from scratch, wrote
a new version of it based on an existing lockfile found or left it unchanged.
The latter happened whenever the existing \code{package-lock.json} was already
in sync with dependency constraints specified in project's \code{package.json}.
It can be noted that npm would also automatically use an
\code{npm-shrinkwrap.json} file over \code{package-lock.json} if the former were
present. However, this was not the case for any of the npm projects tested.
\lstinputlisting[
float=htpb,
language=shell-command,
caption=The npm command used to produce an up-to-date lockfile.,
label=lst:npm-uninstall
]{npm-uninstall.txt}
For projects that utilize workspaces, attempt was made to also add
workspace-related options \code{-}\code{-workspaces},
\code{-}\code{-include-workspace-root}, and
\code{-}\code{-workspace} as appropriate to \code{npm uninstall}
and subsequent npm invocations. Workspaces are a feature that allows multiple
subprojects to be developed in subdirectories of a single npm parent project,
with the parent and each subproject having its own \code{package.json}
file. Despite the effort, all workspaced projects that were tested failed to
build for other reasons. Several tested projects were found to use workspaces
for smaller satellite utilities while having the project's package described by
the \code{package.json} file in the root directory of the repository.
Those were built without any workspace-specific npm options.
A minimal server, written for this experiment, listened for HTTP requests on
port 8080 inside the network-isolated build environment. It received npm
package metadata requests and passed the requested package names via a fifo to a
service running outside the container. The service downloaded the metadata and
filtered it to only contain information about package versions published before
\tresholdDate{}. The original npm distribution tags were stripped, but a mock
\code{latest} tag was added for every package, pointing at its newest
non-pre-release version from before \tresholdDate{}. Pruned pieces of metadata
were supplied to the guest-side server for use as responses to the npm tool.
\subsection{Remaining build steps}
After successful dependency resolution, packages listed in the lockfile were
installed with the help of an \code{npm ci} command, as shown in
Listing~\ref{lst:npm-ci}. Analogously to the dependency resolution step,
package file requests were sent through the HTTP protocol to the local port 8080
and were handled by the guest-side server, which in turn relied on the host-side
service to perform the actual downloads on guest's behalf.
\lstinputlisting[
float=htpb,
language=shell-command,
caption=The npm command used to install dependencies.,
label=lst:npm-ci
]{npm-ci.txt}
Successful installation of dependencies was followed by an invocation of a
\code{build} action that npm projects conventionally define in their
\code{package.json} files. The command used is shown in
Listing~\ref{lst:npm-run-build}.
\lstinputlisting[
float=htpb,
language=shell-command,
caption=The npm command used to invoke project-specific build operations.,
label=lst:npm-run-build
]{npm-run-build.txt}
At this point, the \code{package-locks.json} file was copied to a subdirectory
of the results directory to be persisted after experiment's end. The same was
done at subsequent builds, described further below, which involved modifications
to the dependency tree. The collected lockfiles later allowed calculation of
dependency tree sizes. When dependency tree modifications were found to cause
changes to the built package, these lockfiles were also useful in understanding
the exact reasons behind those changes.
As of \tresholdDate{}, built npm packages are distributed as \code{.tgz} archive
files. In the jargon they are called ``tarballs'' and in case of npm packages
they are compressed using gzip algorithm. An \code{npm pack} command exists
which can produce such archive from project's files. Although the same could be
achieved with a traditional tar program, the npm's command is convenient,
because -- among others -- it automatically omits unneeded files like the
\code{node\_modules} directory. The exact form of the command used to persist
the built package is shown in Listing~\ref{lst:npm-pack}.
\lstinputlisting[
float=htpb,
language=shell-command,
caption=The npm command used to create the built package file.,
label=lst:npm-pack
]{npm-pack.txt}
\subsection{Repeated builds without upstream lockfiles}
For a project that was successfully built with the described procedure, the
process was repeated with alterations. Upon each repetition, the repository was
brought to a clean state and had added Git hooks -- if any -- removed. However,
re-creation of the entire semi-isolated environment was deemed unnecessary for
the purpose of the experiment. After the repository was cleaned, each repeated
build started with the Git revision checkout attempts described earlier.
The first alteration of the build was the removal of existing lockfiles
recognized by npm or its alternatives: \code{npm-shrinkwrap.json},
\code{package-lock.json}, \code{yarn.lock}, and
\code{pnpm-lock.yaml}. It happened right after the removal of
version-controlled \code{node\_modules} and \code{dist} directories.
The removal of lockfiles was done to force a full dependency resolution. If
successful, the build in this form was performed twice to check if dependency
resolution and lockfile generation in npm suffer from obvious nondeterminism
issues.
Additionally, all later builds of the project also involved the removal of
existing lockfiles, besides other alterations.
\subsection{Elimination of unnecessary direct dependencies}
Each project known to build successfully with and without the removal of its
version-controlled lockfile -- if any -- was tested further. The experiment
checked whether it had the ability to build with each of its direct dependencies
-- tried in reverse alphabetical order -- removed. E.g., a project with nine
direct dependencies specified in its \code{package.json} -- including those
listed as \code{dependencies}, \code{devDependencies}, and
\code{optionalDependencies} but not \code{peerDependencies} -- was built nine
times, each time with another direct dependency removed for the first time. The
build was considered successful when the npm commands all finished with zero
status. For each such successful build the tested dependency was recorded as
unnecessary and was also removed in all subsequent build attempts, together with
the dependency tested in a given attempt. E.g., if five out of first eight
dependencies were found to be unnecessary, then subsequent build was performed
with the ninth dependency plus the initial five removed. I.e., a total of six
dependencies were removed in that build.
The removal consisted of erasing of dependency's entry in project's
\code{package.json} file right after lockfiles deletion. However, the original
\code{package.json} contents were always recorded and restored before the
\code{npm pack} invocation. This was done to have the built package tarballs --
each of which contains a copy of the \code{package.json} -- easier to compare
for other differences. Interestingly, for some projects the \code{npm pack} did
not place the \code{package.json} inside the tarball verbatim and instead
generated a variant of that file with some fields changed in a way custom to the
project. One such case, concerning the \code{@testing-library/user-event}
package, is discussed in~\ref{sub:apparently-disfunctional-pkgs}.
All later builds of the project also involved the removal of dependencies
identified at this point and the described restoration of the original
\code{package.json} file.
\subsection{Elimination of unnecessary indirect dependencies}
With all apparently-unnecessary direct dependencies identified, the remaining
indirect dependencies were tested. For it is unstraightforward to forcibly
remove an indirect dependency from npm project's dependency tree, a choice was
made to instead attempt ``dummifying'' it. The npm feature of overrides --
mentioned in~\ref{sub:effects-of-semver} -- was used to force the npm's
resolution algorithm to always select a mocked, dummy version
``0.0.0-msc-experiment-dummy'' of a given dependency. At the same time, for the
dependency package meant to be dummified, the local server providing packages'
files and metadata on port 8080 would not respond with that package's real
metadata. Instead, it would give a response indicating that the only available
version of that package is the dummy version, which has no own dependencies.
Additionally, it would serve the corresponding dummy package tarball with only
minimal contents.
This process of identifying project's unnecessary indirect dependencies was
analogous to that concerning direct dependencies. It involved multiple builds
-- more than a thousand in case of one npm project tested. In each build a
single tested indirect dependency -- together with the unnecessary indirect
dependencies identified previously -- was dummified. Each time the overrides
were added to project's clean \code{package.json} file. The addition of
overrides was carried out together with the removal of unnecessary direct
dependencies from \code{package.json}. Build's all npm commands had to finish
with zero status for the tested dependency to be assumed dummifiable. Each time
the \code{package-lock.json} from the last successful build was consulted to
determine the next dependency to test. Applicable dependencies were tried in
reverse alphabetical order.
All later builds of the project also involved the dummification of indirect
dependencies identified at this point. During the entire experiment, whenever a
dependency to override already had an upstream override specified in
\code{package.json}, the original override was being removed.
\subsection{Elimination of dependency conflicts}
Even after the elimination of unnecessary direct and indirect dependencies,
project's dependency tree could still contain extraneous conflicting
dependencies. Subsequent builds were carried out to forcibly remove those
conflicts where possible, utilizing overrides. For every dependency that
occured multiple times in multiple versions in the tree, a build attempt was
made with an override which forced that package to be always used in the same,
single version.
\begin{itemize}
\item
If it happened to be both a direct and indirect dependency of the project --
it was overriden with the version that was previously used to satisfy
project's direct dependency.
\item
If it was only an indirect dependency -- it was overriden with the highest of
the versions in which it previously appeared.
\end{itemize}
Just like before, the build was repeated to identify every dependency conflict
that -- when forcibly removed -- does not cause any npm invocation finish with
non-zero status.
\section{Build attempt results}
\label{sec:build-attempt-results}
Two projects were found not to actually exist as real pieces of software. I.e.,
their npm packages were placeholders. Another \skippedDueToLimitationsCount{}
projects could not be tested due to limitations of experment's environment --
they used dependency packages that are distributed through servers other than
the official npm Registry. This made the npm tool attempt downloading these
directly, which failed in a network-isolated environment. The results from
build attempts of the final \allTestedCount{} projects are presented in
Figure~\ref{fig:status-counts}. Different types of failures were classified
based on the first error reported in the build attempt. It means that, e.g., a
project with unresolvable dependencies and a missing \code{build} action was
classified as failing at the dependency resolution step.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{status-counts.svg}
\caption{Statuses of automated hermetized build of top npm projects.}
\label{fig:status-counts}
\end{figure}
\subsection{Projects whose source repositories failed to be cloned}
For projects in this category, sources could not be automatically retrieved.
Either no repository URL was included in published npm metadata of the package
version or the published URL was not valid.
Some packages were found to provide SSH URLs to their projects' GitHub
repositories. Such URLs could not be used for anonymous cloning, despite the
repositories themselves being -- at least in some cases -- public and
anonymously cloneable through HTTP. A sample Git error message is presented in
Listing~\ref{lst:ssh-clone-fail}. It was printed upon an attempt to use the
\code{ssh://git@github.com/sinonjs/sinon.git} URL in a \code{git clone} command.
\lstinputlisting[
float=htpb,
caption=Error reported by Git upon an attempt to clone a repository using an
SSH URL.,
label=lst:ssh-clone-fail,
numbers=none
]{ssh-clone-fail.txt}
There was also a single case where an HTTP URL pointed at a repository that no
longer existed. Other interesting unworkable URLs were ones with a branch name
appended\footnote{e.g., \code{https://github.com/emotion-js/emotion.git\#main}}.
Some unworkable URLs were also pointing to web pages of repositories'
subdirectories\footnote{e.g.,
\code{https://github.com/babel/babel/tree/master/packages/babel-core/}}. In a
vast majority of cases a correction of URL with the help of a simple regular
expression could be attempted. Interestingly, none of the tested projects were
found to use a VSC other than Git.
\subsection{Projects whose relevant source control revisions were not found}
For projects in this category, the git source repository could be cloned but it
contained neither the commit specified in package's metadata nor a tag
corresponding to the version number being built. Reasons included
\begin{itemize}
\item
VCS revisions being tagged differently, e.g., \code{PACKAGE-NAME@VERSION},
\item
particular version's tag being missing, and
\item
tags not being used altogether.
\end{itemize}
\subsection{Projects that do not follow the conventions}
\label{sub:packages-not-following-conventions}
Projects in this category either lacked a \code{package.json} file in
repository's root or lacked a \code{build} action.
Size of this category seems to suggest that the conventions which we and others
\cite{goswami-reproducibility} rely upon are very loosely followed. However,
some projects classified here are trivial ones that simply do not require any
operations to be performed as part of a \code{build} action. For example,
package \code{semver}, as distributed through the npm Registry, was found to
only contain files that are present in its project's source repository. I.e.,
none of the files were created or modified as part of the build process
performed by that project's developers. The files in \code{semver}'s built
package archive were found identical to those in the relevant revision of the
source repository, with the repository additionally holding some other files,
e.g., test scripts. \code{semver} does indeed not require compilation nor
similar build steps. It has no need for a \code{build} action and therefore
does not have one specified in its \code{package.json} file.
\subsection{Projects with dependency resolution failures}
\label{sub:resolution-failures}
Projects in this category had the \code{npm uninstall} command fail to
create or update the lockfile. The predominant source of failure is related to
peer dependency resolution, with a sample error message shown in
Listing~\ref{lst:eresolve-error}. Simplifying, peer dependencies are a feature
through which developers can forbid npm from creating a dependency conflict with
a particular package. Typically, an add-on package specifies its base package
-- which it enhances -- as its peer dependency. If the base package were
specified as add-on's casual dependency, npm's resolution algorithm could make
the add-on package use its own copy of that base package. This is typically not
the behavior the developer or user wants. Peer dependencies are a mean to
prevent it.
\lstinputlisting[
float=htpb,
caption=Error reported upon peer dependency resolution failure during
\code{ts-node} project build.,
label=lst:eresolve-error
]{eresolve-error.txt}
The exact behavior of peer dependencies changed through the history of npm. One
alternative package manager for the npm ecosystem -- Yarn -- is also known for
behaving different than npm in some situations. It is suspected that most of
the projects in this category could have their dependencies resolved
successfully with older version of npm or with Yarn. It was found that
\failedToResolveAndUsingYarnCount{} packages in this category do have a
\code{yarn.lock} file in the VSC, indicating their developers likely use
Yarn over npm.
\subsection{Projects with invalid upstream lockfiles}
The \code{npm uninstall} command was invoked during every project build to make
sure an up-to-date lockfile is in place. Despite that, for two packages a
lockfile was left behind that \code{npm ci} later reported as invalid due to
being out of sync with project's \code{package.json}. One of these projects had
a preexisting \code{package-lock.json} file and the other had a \code{yarn.lock}
file\footnote{npm also reads a \code{yarn.lock} when no other lockfile is
present}.
\subsection{Projects that expect network access to build}
\label{sub:expect-network-access}
Projects in this category failed to build due to unsuccessful network request
attempts other than the attempts mentioned at the beginning
of~\ref{sec:build-attempt-results}.
The majority of build failures in this category occured when project's
development dependency was trying to download a web browser binary for
browser-based tests. Examples of other non-npm resources that projects tried to
download were font files from Google Fonts and sources for automated native
compilation of a library whose Node.js bindings package was being installed.
It can be stated that network accesses during npm project builds are commonly
made to facilitate installation of architecture-specific software binaries, as
these are inconvenient to distribute through the architecture-agnostic npm
Registry.
\subsection{Projects that require a build tool other than npm}
Projects in this category are known to require either Yarn or pnpm to build.
They could be classified with certainty because either
\begin{itemize}
\item
their \code{package.json} files contained special URLs or package names that
npm could not handle, or
\item
their build processes printed messages that explicitly informed the developer
about the need to use a particular tool.
\end{itemize}
There are many more projects which likely rely on Yarn or pnpm but could not be
classified here with certainty, see~\ref{sub:resolution-failures}.
\subsection{Projects with additional non-npm dependencies}
Projects in this category need additional tools that are not installable through
npm. Unlike projects mentioned in~\ref{sub:expect-network-access}, these rely
on the developer to install the additional tool.
Experiment logs indicated failures upon searching for Python executable and for
configuration files of popular shells.
\subsection{Projects with other build failures}
Projects in this category failed to build due to reasons other than those
discussed up to this point. Failures occured due to problems like missing
modules, missing variable, and an operation hanging indefinitely.
\subsection{Projects that could be built only when using upstream lockfiles}
Projects in this category failed to build only after their upstream lockfiles
were removed. After seemingly successfult dependency resolution, errors were
raised during TypeScript compilation. The errors almost certainly resulted from
newer versions of project's dependencies being used. This occured despite the
use of Semantic Versioning and the respecting of dependency constraints declared
by projects.
\subsection{Projects built with both upstream and re-generated lockfiles}
Packages in this category are considered to have been built successfully,
because all npm command invocations from the first two builds finished with zero
status. There is no guarantee that the packages built are fully functional.
For example, some projects like \code{@testing-library/react} rely on an
additional tool called semantic-release, which is not invoked as part of
\code{npm run build}. That tool is responsible for analyzing project's change
history and determining the right version number to be recorded in project's
\code{package.json} file~\cite{semantic-release}. When its use is omitted, the
built package is reported as having a placeholder version, e.g.,
``0.0.0-semantically-released''.
It is expected that a more polished and defect-free build process would often
involve a dependency tree of several more or several less packages than in this
experiment. Nonetheless, it was assumed that dependency sets found necessary
for successful \code{npm install} and \code{npm build} invocations do
represent the characteristics of the projects well enough.
Results presented through the rest of this chapter concern the dependency trees
of projects from this very category.
\section{Dependency trees after removals of dependencies and their conflicts}
\label{sec:trees-after-pruning}
The sizes of the original dependency trees, produced in project builds with
upstream lockfiles removed, are shown in Figure~\ref{fig:tree-size-stats},
together with the sizes of pruned trees. Each pair of boxes represents the
experiment at a different stage. The left box of each pair shows the average
number of project dependencies where all distinct versions of the same package
are counted. E.g., an npm package \code{foo} that occurs in a dependency tree
three times as \code{foo@1.2.3}, \code{foo@2.1.0}, and again \code{foo@2.1.0} is
counted as two. The right box of each pair shows the average number of
dependencies with all versions of a single package counted as one. E.g., the
\code{foo} introduced before is now counted as one. Standard deviation of the
sample is additionally plotted over every box.
Individual projects' dependency tree sizes are plotted as circles over every
box. \inDebianCount{} projects were found to also have their corresponding
packages present in Debian Bookworm as of \debianTresholdDate. They are
represented by filled, black circles. No clear relation between dependency tree
sizes and presence in Debian can be seen at any stage of the experiment. Also
consult Figure \ref{fig:tree-size-stats-no-bc} for a variant of this plot that
omits builds of packages which appear to be nonfunctional due to aggressive
dependency elimination.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{tree-size-stats.svg}
\caption{Dependency tree sizes of built npm projects.}
\label{fig:tree-size-stats}
\end{figure}
\section{Dependency conflict counts}
\label{sec:dep-conflict-counts}
Projects were further categorized by the number of dependency conflicts that
could not be removed with the method used. The categories are visualized in
Figure~\ref{fig:unflattened-multiver-counts}. Counts of all projects and counts
of projects having corresponding packages in Debian are shown. Also consult
Figure \ref{fig:unflattened-multiver-counts-no-bc} for a variant of this plot
that omits builds of packages which appear to be nonfunctional due to aggressive
dependency elimination.
As can be seen, most of the projects had few to no remaining dependency
conflicts. Once again, there was no clear relation between the number of
remaining dependency conflicts and presence in Debian. Given this
distribution's norms, this suggest that the authors of Debian packaging likely
managed to further remove some conflicts that could not be eliminated with the
experiment's method. They possibly used more invasive methods like source code
patching.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{unflattened-multiver-counts.svg}
\caption{Counts of built projects with different numbers of unremovable
dependency conflicts.}
\label{fig:unflattened-multiver-counts}
\end{figure}
\section{Differences in build outputs produced during the experiment}
The repeated builds with upstream lockfiles removed had their produced package
tarballs and generated \code{package-lock.json} files compared. The files
produced on two build runs were found identical in case of every successfully
built project\footnote{npm authors should be credited for making \code{npm pack}
produce tarballs without nondeterministic timestamps}. This does not yet
guarantee that the builds and dependency resolutions are reproducible. However,
it does indicate that differences found after dependency removals, etc.\ are
likely the effect of those alterations and not manifestations of builds
nondeterminism.
It was found that \withAnyTarballsDifferentCount{} out of
\builtSuccessfullyCount{} successfully built projects had their package tarballs
differ as the result of either dependency removals, dummifications, or conflict
removals. All these cases were manually inspected. Two differences were found
to be caused by reordered \code{package.json} entries and appear to be mere
artifacts of this experiment's method of restoring project's original
\code{package.json} file before \code{npm pack} invocation. Some of the more
interesting cases are discussed below.
\subsection{Use of a different dependency version}
\label{sub:use-of-different-dep-ver}
Several times an alteration of the build process allowed the npm's resolution
algorithm to use a newer version of a dependency which then caused generation of
different but still correct code. One example is the \code{concurrently}
console application written in TypeScript. Package \code{typescript}, providing
a TypeScript compiler, was specified as its direct development dependency.
During the experiment this direct dependency was removed, but package
\code{typescript} still made its way to the dependency tree due to being
required by another dependency -- \code{@hirez\_io/observer-spy}. Its
constraint on \code{typescript}'s version was looser than that present before,
causing version 5.8.3 to be used instead of former 5.2.2. A sample of changes
caused by the use of that newer TypeScript compiler is presented in
Listing~\ref{lst:newer-typescript-changes}.
\lstinputlisting[
float=htpb,
language=diffoscope,
caption=Excerpt from diffoscope's report of differences in built
\code{concurrently} package tarballs.,
label=lst:newer-typescript-changes,
numbers=none
]{newer-typescript-changes.diffoscope}
It is worth noting that the dependency \code{@hirez\_io/observer-spy} -- even
if not necessary by itself -- could not be eliminated with this experiment's
method.
\subsection{Inlining of a dependency}
\label{sub:inlining-of-a-dep}
One similar case was that of built \code{axios} package, which -- besides
also showing generated code differences resulting from changed compiler/bundler
version -- had its dependency \code{proxy-from-env} treated differently,
despite always occuring in the same version 1.1.0. Initially,
\code{proxy-from-env} was specified as \code{axios}' runtime
dependency and was merely referenced from the code being generated during build.
When, as part of the experiment, \code{proxy-from-env} was removed as
project's direct dependency, it remained present in the dependency tree due to
being required by certain development dependency. \code{proxy-from-env}
was therefore itself flagged as an indirect development dependency, which made
the bundler treat it differently and inline it in \code{axios}' generated
code.
\subsection{Digest included in the generated package}
If project's generated files include a hash of its dependency specifications or
a similar derived value, it is an obvious source of difference in this
experiment. One of such projects is \code{ts-jest}, which places a digest
like \code{4ec902e59f1ac29ff410d624dcccf9b192920639} in a
\code{.ts-jest-digest} file inside its package tarball.
\subsection{Apparently disfunctional built packages}
\label{sub:apparently-disfunctional-pkgs}
Several times a change to project's dependency tree did actually cause a
significant change to the build output. In multiple cases, a removed package
could not be found by a bundler tool called Rollup, which then treated it as an
``external'' dependency than need not be bundled. Rollup merely issued a
warning about a reference to the now-absent code module and proceeded without
it. An example of this can be seen in Listing
\ref{lst:warning-module-as-external} with an excerpt from the log of
\code{rollup-plugin-typescript2} project build.
\code{rollup-plugin-typescript2} specified package \code{object-hash} as a
development dependency and had its code included in an amalgamated script file
generated by Rollup. After \code{object-hash} was removed, the invocation of
\code{rollup-plugin-typescript2}'s build action still finished with zero status,
with the generated amalgamated script file being smaller by the size of the
missing dependency. If the \code{rollup-plugin-typescript2} package built this
way were to be later used, its code would likely encounter an error when trying
to import the \code{object-hash} module.
\lstinputlisting[
float=htpb,
caption=The output of \code{npm run build} invocation with a missing
dependency reported by Rollup.,
label=lst:warning-module-as-external
]{warning-module-as-external.txt}
A single interesting case was that of \code{@testing-library/user-event} project
and the \code{package.json} file generated for its package tarballs. Several --
seemingly vital -- \code{package.json} keys were no longer present after
project's \code{typescript} dependency was removed. The change caused by
\code{typescript}'s removal is shown in
Listing~\ref{lst:removed-typescript-changes}).
\lstinputlisting[
float=htpb,
language=diffoscope,
caption=Excerpt from diffoscope's report of differences in
\code{package.json} files inside built
\code{@testing-library/user-event} package tarballs.,
label=lst:removed-typescript-changes,
numbers=none
]{removed-typescript-changes.diffoscope}
In some cases, as subsequent dependencies of a project were eliminated, a
bundler tool combined the dependencies in a different order, making amalgamated
scripts difficult to compare with diff-like tools. There were also cases where
the size of individual generated files would increase by an order of magniture
or even go up and down during a series of builds. One suspected reason for
increasing amalgamated script size -- besides the one discussed in
\ref{sub:inlining-of-a-dep} -- is polyfilling. It is the action of replacing
newer JavaScript language constructs used by programmers with code that is
compatible with older language runtimes. An older version of a build tool would
typically aim to support more legacy runtimes, applying more polyfills and
increasing the produced script sizes as a result. Nonetheless, for the purpose
of this experiment, whenever the nature and effect of changes in a build output
were unclear, the package was considered one of the total of eight disfunctional
packages.
\subsection{Updated statistics}
We are interested in the relation between project's dependency tree
characteristics and its packagability for software distributions. The
statistics presented in \ref{sec:trees-after-pruning} and
\ref{sec:dep-conflict-counts} included eight projects with assumed
disfunctionalities introduced by this very experiment. Three of these do have
corresponding Debian packages. As these eight cases could make our results
deceptive, the statistics are now presented again, with problematic projects not
taken into account. Dependency tree sizes at various stages of the experiment
are presented in Figure \ref{fig:tree-size-stats-no-bc}. Projects'
categorization by the number of remaining dependency conflicts is visualized in
Figure~\ref{fig:unflattened-multiver-counts-no-bc}.
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]{tree-size-stats-no-bc.svg}
\caption{Dependency tree sizes of built npm projects. Packages which appear
to be nonfunctional due to aggressive dependency elimination are not
included.}
\label{fig:tree-size-stats-no-bc}
\end{figure}
\begin{figure}[htpb]
\centering
\includesvg[width=\linewidth,inkscapelatex=false]
{unflattened-multiver-counts-no-bc.svg}
\caption{Counts of built projects with different numbers of unremovable
dependency conflicts. Packages which appear to be nonfunctional due to
aggressive dependency elimination are not included.}
\label{fig:unflattened-multiver-counts-no-bc}
\end{figure}
As one can see, even these ``cleaned'' results show no relation between
project's dependency tree sizes and its Debian presence.
\chapter{Conclusions}
The results of conducted experiment allow the questions stated at the beginning
of \ref{chp:experiment} to be answered.
\section{Naming the main hindrance to packaging the npm ecosystem}
\label{sub:naming-the-hindrance}
We expected that huge dependency trees and presence of conflicting dependencies
are the major obstacles to packaging npm projects into reproducibility-focused
software distributions. The experiment results show the contrary. If this
hypothesis were true, we would see npm projects with more complex dependency
trees less frequently packaged into Debian -- but there is no such relation.
What are then the most likely reasons for relatively small number of software
from the npm ecosystem in Debian and GNU Guix? For the latter, the challange of
bootstrapping several popular, self-depending build tools appears relevant.
Five of these were mentioned in \ref{sub:self-depending-software}. As of
\debianTresholdDate{}, four of them -- \code{typescript}, \code{@babel/core},
\code{rollup}, and \code{gulp} -- are present in Debian, albeit under different
names. The Debian packages of all four were also found to depend on themselves
to build. Since GNU Guix' policies make it more difficult to add self-depending
packages to the distribution, this explains the drastically different coverage
of the npm ecosystem by these system software distributions.
Aside from that, the incompatibility of JavaScript developers' workflows with
system software distribution packages -- as highlighted
in~\ref{sec:inconvenience-of-distros} -- should be considered the major issue.
\section{Developer-supplied lockfile being infrequently necessary}
As found, only two tested projects could be built with an upsteam lockfile but
failed when it was re-generated. Meanwhile, \builtSuccessfullyCount{} packages
were built successfully in both ways. This is consistent with the expectations.
Repetition of the dependency resolution is not a likely source of build
failures.
\section{Indispensibility of direct and indirect npm build dependencies}
It was found that a non-negligible subset of both direct and indrect npm project
dependencies is unnecessary for a successful build. The effect of removal of
unnecessary direct dependencies can be comprehended by comparing the leftmost
two pairs of boxes in Figure~\ref{fig:tree-size-stats-no-bc}. There is on
average an almost triple reduction in dependency tree sizes, although with a
huge variance. The average number of direct dependencies shrank from
\allDirectDepsAvg{} with sample standard deviation of \allDirectDepsStdDev{} to
\necessaryDepsAvg{} with sample standard deviation of~\necessaryDepsStdDev{}.
Comparing the second and third pair of boxes in Figure
\ref{fig:tree-size-stats-no-bc} shows that almost a half of projects' remaining
indirect dependencies is also not necessary during build, again with a huge
variance. The experiment's automated method of determining the unnecessary
dependencies was not perfect, as shown in~\ref{sub:use-of-different-dep-ver},
but sufficient to allow a conclusion that during packaging, the elimination of
both kinds of dependencies can be worth attempting.
\section{Typical dependency tree sizes of npm projects}
\label{sec:typical-dep-tree-sizes}
The average sizes of built projects' dependency trees ranged from \origTreeMin{}
to \origTreeMax{} with sample standard deviation of~\origTreeStdDev{}, as shown
in Figure~\ref{fig:tree-size-stats-no-bc}. With the experiment's method, it was
possible to reduce the tree sizes by about a ratio of five on average.
The final dependecy tree sizes of about $160$ are not drastically higher than
those in other software ecosystems. For example, as of \debianTresholdDate,
Debian package \code{python-xrt} was found to be built in an environment
with $180$ installed packages named \code{python-*}, as evidenced in its
\code{.buildinfo} file.
It is worth noting that the numbers discussed here and in the following section
might be representative of only the more complex npm packages. As explained
in~\ref{sub:packages-not-following-conventions}, there can be many popular npm
projects like \code{semver} that do not require an actual \code{build} action,
likely have fewer declared dependencies, and likely only require the npm tool to
create the package tarball.
\section{Frequency of dependency conflicts in npm projects}
Among the npm projects built successfully, only one had no conflicting
dependencies in its original tree. This shows that dependency conflicts are
indeed a normal and accepted thing in the npm ecosystem.
In the original dependency trees, the count of dependencies in conflict averaged
at \origTreeMultiverAvg{} and sample standard deviation
was~\origTreeMultiverStdDev{}. In case of more than half of the projects the
conflicts were completely eliminated. Several cases of unremovable conflicts
remained, as can be sees in Figure~\ref{fig:unflattened-multiver-counts-no-bc}.
However, this part of the results should not be considered entirely
representative of the real state of affairs, as explained
in~\ref{sec:dep-conflict-counts}. It is expected that through manual work the
build process of many more npm packages can be made free of dependency
conflicts.
\section{Package disfunctionality caused by dependency tree reduction}
As witnessed in~\ref{sub:apparently-disfunctional-pkgs}, there is a
non-negligible number of cases where forced removal of direct or indirect
dependencies causes built package to lack important pieces of code or have other
deficiencies. Many of these problems were caused by Rollup bundler's liberal
treatment of missing code modules and could be automatically detected, for
example by searching the build logs for specific strings.
Nevertheless, the risk of building disfunctional packages appears relatively
high, which is not acceptable if this experiment's method were to be used for
preparation of package recipes in a reproducibility-oriented software
distribution. Since in more than half of all cases the diffoscope's reports on
built package differences were found comprehensible, it is advisable to manually
investigate dependency removals whose effects are unclear.
Additionally, the method itself proved to have a weakness of allowing a removed
direct dependency to still appear as an indirect dependency, as shown in
\ref{sub:use-of-different-dep-ver} and~\ref{sub:inlining-of-a-dep}. Although
this does not appear to have lead to built packages' disfunctionalities during
the experiment, it is a space for improvement. One simple solution would be to
eliminate direct dependencies through dummification, as it was already done with
indirect ones.
\section{Relevance of npm package distribution tags for successful dependency resolution}
The dependency resolution failures described in \ref{sub:resolution-failures}
were all manually analyzed and none was found to be caused by a dependency
specification referencing a distribution tag omitted in the experiment. Four of
the built projects were found to have a direct or indirect dependency specified
by the \code{latest} tag. Among others, \code{typescript} -- the most popular
npm package according to the ranking in~\ref{chp:most-popular-dev-deps} --
requires its direct development dependency \code{@types/node} to be in version
tagged \code{latest}.
Concluding, the special \code{latest} tag should be present in npm
dependency metadata to avoid needless dependency resolution failures.
Fortunately, it can usually be derived from the available package versions. All
other tags can in the vast majority of cases be omitted from the dependency
resolution matadata, removing the need to rely on external, mutable npm
distribution tags information.
\section{Prototype for npm dependency resolution under Paradigm 3}
The experiment's environment resembled that proposed in \ref{sec:paradigm-3} for
Paradigm 3 for hermeticity and reproducibility. The approach with a host-side
service performing requests on behalf of the isolated guest was indeed workable.
The experiment also showed that this prototype could benefit from added ability
to provide the guested npm process with dependency package files hosted on
different sites than just the npm Registry. This would require additional work
to have npm's package tarball requests reach the locally-running service. A
solution could involve configuring npm to use a TLS-enabled HTTP proxy in the
likes of mitmproxy~\cite{mitmproxy}. While burdensome, it should be workable.
At the same time, obtained results did not contain the expected indicators that
Paradigm 1 -- and Paradigm 2 with flat input metadata of the dependency
resolution step -- is insufficient in practice for handling the complex npm
ecosystem. This means that new paradigms, as proposed in this work, are not
necessary for further progress in the field of reproducible software builds.
However, paradigms 3 and 4 can still prove useful in addressing the
bootstrappability and developer usefulness issues named
in~\ref{sub:naming-the-hindrance}.
\chapter{Summary}
Throughout the course of this work it was found that software industry shows
some modest interest in reproducible builds. Practical difficulties in applying
reproducibility to software projects hinder popularisation of this security
measure. Software developed around popular technologies must become easier to
rebuild hermetically and to test for reproducibility. This will allow
reproducible builds to be more broadly recommended and mandated.
Even though the concept of end user verification of build reproducibility offers
increase in security confidence, years after 2018 saw little progress in its
application. Due to the issues of rebuilder lag and occasional build
nondeterminism, continuous tests performed independently of end users should be
considered a more practically viable security measure.
Even when build reproducibility is aimed and tested for, software distributions'
approaches differ. Metadata used to reproduce Debian packages was found
insufficient to also reproducibly verify the results of dependency resolutions
that package builds relied on. This is not a severe vulnerability. However, it
motivates increased interest in purely functional package managers, whose design
excludes the possibility of such ``verification hole'' occuring.
Contrary to intuition, traditional software packaging scheme of Debian can be
applicable even to npm software with complex dependency graphs. One could still
attempt to utilize suggested Paradigm 3 or 4 to replace existing approaches of
Debian and GNU Guix. However, such efforts would offer no certain benefit.
Although npm packages tend to have large dependency tree sizes and conflicting
dependencies, this is not the ultimate reason for almost zero coverage of the
npm ecosystem by GNU Guix. Instead, the issues of package bootstrappability
appear to be the determining factor. These, however, are practically solvable.
The packages in reproducible software distributions must be bridged with
developers' preferred workflows. If this does not happen, the distributions
will not only be slow in including software from the npm Registry and similar
repositories. The software already in those distributions will fail to bring
the security benefits that it could.
As long speculated, much of declared dependencies of a typical npm project are
not needed to build it. It was found that many indirect dependencies are also
unnecessary. Their omission is crucial both to simplify packaging into software
distributions and to reduce the software supply chain attack surface.
\chapter{Future work}
During npm project builds analysis it was found that projects exist which
require no code transformations during build. One such case is described in
detail in~\ref{sub:packages-not-following-conventions}. If identified,
projects from this category could be packaged hermetically and reproducibly with
minimal effort. Automated identification of such projects could be a future
research goal.
After the experiment, bootstrappability was named a likely major reason for
small coverage of the npm ecosystem by GNU Guix. The finding of viable and
optimal bootstrap chains of npm packages could therefore be the subject of
another research.
Paradigms 3 and 4 for hermeticity and reproducibility were proposed to address
the issue of incomprehensibly complex dependency relations between npm packages.
It was found that in the context of reproducible builds, the issue is resolvable
even without employing these paradigms. However, it is yet to be checked --
possibly in a new work -- whether these paradigms can actually make software
packaging process less labor-intensive and therefore more efficient.
This work touches the topic of securing the inputs of software builds. The
applicability of methods like the suggested canaries could be further
investigated.
A subset of tested projects did not have their VCS revisions tagged in the
expected way. The tagging habits of developers and means of automated
identification of VCS revisions corresponding to releases could be researched.
A possible approach to solving the problem of missing VCS tags could involve
comparing commit dates with package version release dates. If devised, a
successful method would benefit VCS-based software packaging, which appears
desirable in the light of the XZ backdoor.
npm developers are not incentivized make their software easily bootstrappable.
Proof of concept of Ken Thompson's Trusting Trust attack~\cite{Thompson:1984}
could be presented for one or more popular npm packages. It could help raise
awareness of the supply chain issues and make the community interested in
rebuildability and ultimately bootstrappability. The PoC could be a
self-implanting backdoor in one of the self-depending builds tool.
\clearpage
\phantomsection{}
\addcontentsline{toc}{chapter}{\refname}
\printbibliography
\end{document}
