Software Heritage Analyzing the Global Graph of Public Software Development

Software Heritage Analyzing the Global Graph of Public Software Development Stefano Zacchiroli Université de Paris & Inria — [email protected], @zacchiro 19 May 2021 Team ACES — Télécom Paris (online) THE GREAT LIBRARY OF SOURC E CODE Stefano Zacchiroli Software Heritage 2021-05-19, ACES 1 / 40 About me Associate Professor (Maître de conférences), Université de Paris on leave (délégation) at Inria Free/Open Source Software activist (20+ years) Debian Developer & Former 3x Debian Project Leader Former Open Source Initiative (OSI) director Software Heritage co-founder & CTO Research path 1Formal methods for ensuring the quality of software upgrades (Mancoosi project) Industry adoption: Debian, OPAM, Eclipse P2 2Formal methods for automated upgrade planning in the cloud (Aeolus project) Industry adoption: Mandriva, Kyriba 3Large-scale software evolution analysis (Debsources platform) 4Very-large-scale source code analysis and preservation (Software Heritage)  this talk Stefano Zacchiroli Software Heritage 2021-05-19, ACES 2 / 40 About me Associate Professor (Maître de conférences), Université de Paris on leave (délégation) at Inria Free/Open Source Software activist (20+ years) Debian Developer & Former 3x Debian Project Leader Former Open Source Initiative (OSI) director Software Heritage co-founder & CTO Research path 1Formal methods for ensuring the quality of software upgrades (Mancoosi project) Industry adoption: Debian, OPAM, Eclipse P2 2Formal methods for automated upgrade planning in the cloud (Aeolus project) Industry adoption: Mandriva, Kyriba 3Large-scale software evolution analysis (Debsources platform) 4Very-large-scale source code analysis and preservation (Software Heritage)  this talk Stefano Zacchiroli Software Heritage 2021-05-19, ACES 2 / 40 Outline 1Software Heritage 2Querying the archive 3Graph compression 4Security synergies and outlook Stefano Zacchiroli Software Heritage 2021-05-19, ACES 3 / 40 Software Heritage in a nutshell www.softwareheritage.org THE GREAT L I BRA RY OF SO URCE CO D E Collect, preserve and share all software source code Preserving our heritage, enabling better software and better science for all Reference catalog find and reference all software source code Universal archive preserve all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2021-05-19, ACES 3 / 40 Software Heritage in a nutshell www.softwareheritage.org THE GREAT L I BRA RY OF SO URCE CO D E Collect, preserve and share all software source code Preserving our heritage, enabling better software and better science for all Reference catalog find and reference all software source code Universal archive preserve all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2021-05-19, ACES 3 / 40 Software Heritage in a nutshell www.softwareheritage.org THE GREAT L I BRA RY OF SO URCE CO D E Collect, preserve and share all software source code Preserving our heritage, enabling better software and better science for all Reference catalog find and reference all software source code Universal archive preserve all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2021-05-19, ACES 3 / 40 Software Heritage in a nutshell www.softwareheritage.org THE GREAT L I BRA RY OF SO URCE CO D E Collect, preserve and share all software source code Preserving our heritage, enabling better software and better science for all Reference catalog find and reference all software source code Universal archive preserve all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2021-05-19, ACES 3 / 40 An international, non profit initiative Sharing the vision www.softwareheritage.org/support/testimonials Donors, members, sponsors Platinum sponsors Silver sponsors Bronze sponsors Gold sponsors www.softwareheritage.org/support/sponsors Stefano Zacchiroli Software Heritage 2021-05-19, ACES 4 / 40 The archive: a (giant) Merkle DAG origin visit https://forge.softwareheritage.org/source/helloworld.git snapshot 1 https://forge.softwareheritage.org/source/helloworld.git 2 timestamp Fri Feb 9 12:38:45 2018 +0100 Fri Feb 9 13:29:00 2018 +0100 0861db5e… 0861db5e… <<Revision>> a3ee21ad… +author = "Stefano Zacchiroli <zack@…>" +message = "add build toolchain …" +timestamp = Thu Feb 8 10:49:29 2018 +0100 +directory: Directory +parents: Revision list <<Directory>> b94a90cd… +entries ".gitignore" "Makefile" "hello.c" <<Content>> 225ae01b… +data = "all: hello\n\n…" <<Revision>> 43ef7dcd… +author = "Stefano Zacchiroli <zack@…>" +message = "add licensing information and README" +timestamp = Thu Feb 8 10:54:09 2018 +0100 +directory: Directory +parents: Revision list <<Directory>> fa8c0908… +entries ".gitignore" "COPYING" "Makefile" "README.md" "hello.c" <<Content>> a1afd006… +data = "…Yet another…" <<Release>> edf82f21… +author = "Stefano Zacchiroli <zack@…>" +name = "1.0" +message = "1.0 release" +timestamp = Thu Feb 8 15:51:00 2018 +0100 +target <<Snapshot>> 0861db5e… +branches HEAD refs/heads/master refs/tags/1.0 Archive content after visits 1 and 2 <<Content>> c839dea9… +data = "#include …" <<Directory>> 6ca2e444… +entries "hello.c" <<Revision>> 1886826f… +author = "Stefano Zacchiroli <zack@…>" +message = "implement a trivial …" +timestamp = Thu Feb 8 10:44:35 2018 +0100 +directory: Directory +parents: Revision list = None Stefano Zacchiroli Software Heritage 2021-05-19, ACES 9 / 40 The archive: a (giant) Merkle DAG origin visit https://forge.softwareheritage.org/source/helloworld.git snapshot 1 https://forge.softwareheritage.org/source/helloworld.git 2 timestamp Fri Feb 9 12:38:45 2018 +0100 Fri Feb 9 13:29:00 2018 +0100 https://forge.softwareheritage.org/source/helloworld.git 3Fri Feb 9 15:52:50 2018 +0100 510aa88b… 0861db5e… 0861db5e… <<Revision>> a3ee21ad… +author = "Stefano Zacchiroli <zack@…>" +message = "add build toolchain …" +timestamp = Thu Feb 8 10:49:29 2018 +0100 +directory: Directory +parents: Revision list <<Directory>> b94a90cd… +entries ".gitignore" "Makefile" "hello.c" <<Content>> 225ae01b… +data = "all: hello\n\n…" <<Revision>> 43ef7dcd… +author = "Stefano Zacchiroli <zack@…>" +message = "add licensing information and README" +timestamp = Thu Feb 8 10:54:09 2018 +0100 +directory: Directory +parents: Revision list <<Revision>> c7640e8d… +author = "Stefano Zacchiroli <zack@…>" +message = "move source code to src/\n…" +timestamp = Thu Feb 8 15:26:08 2018 +0100 +directory: Directory +parents: Revision list <<Directory>> fa8c0908… +entries ".gitignore" "COPYING" "Makefile" "README.md" "hello.c" <<Content>> a1afd006… +data = "…Yet another…" <<Directory>> 45f0c078… +entries "COPYING" "Makefile" "README.md" "src" <<Release>> edf82f21… +author = "Stefano Zacchiroli <zack@…>" +name = "1.0" +message = "1.0 release" +timestamp = Thu Feb 8 15:51:00 2018 +0100 +target <<Snapshot>> 0861db5e… +branches HEAD refs/heads/master refs/tags/1.0 <<Snapshot>> 510aa88b… +branches HEAD refs/heads/master refs/heads/doc refs/tags/1.0 Archive content after visits 1 and 2 <<Content>> c839dea9… +data = "#include …" <<Directory>> 6ca2e444… +entries "hello.c" <<Revision>> 1886826f… +author = "Stefano Zacchiroli <zack@…>" +message = "implement a trivial …" +timestamp = Thu Feb 8 10:44:35 2018 +0100 +directory: Directory +parents: Revision list = None ... Archive content after visits 1, 2 and 3 Stefano Zacchiroli Software Heritage 2021-05-19, ACES 9 / 40 Archive coverage — archive.softwareheritage.org on disk: ~700 TB (uncompressed); as a graph ~20 B nodes, ~200 B edges the largest public source code archive in the world (and growing!) Stefano Zacchiroli Software Heritage 2021-05-19, ACES 10 / 40 Archive coverage — archive.softwareheritage.org on disk: ~700 TB (uncompressed); as a graph ~20 B nodes, ~200 B edges the largest public source code archive in the world (and growing!) Stefano Zacchiroli Software Heritage 2021-05-19, ACES 10 / 40 Outline 1Software Heritage 2Querying the archive 3Graph compression 4Security synergies and outlook Stefano Zacchiroli Software Heritage 2021-05-19, ACES 11 / 40 Use cases — product needs e.g., for https://archive.softwareheritage.org Browsing ls git log (Linux kernel: 800K+ commits) Wayback machine tarball git bundle (Linux kernel: 7M+ nodes) Provenance tracking commit provenance (one/all contexts) note: requires backtracking origin provenance (one/all contexts) Note: we therefore need both the direct Merkle DAG graph and its transposed Stefano Zacchiroli Software Heritage 2021-05-19, ACES 11 / 40 Use cases — research questions For the sake of it local graph topology connected component size enabling question to identify the best approach (e.g., scale-up v. scale-out) to conduct large-scale analyses any other emerging property Software Engineering topics software provenance analysis at this scale is pretty much unexplored yet industry frontier: increase granularity down to the individual line of code replicate at this scale (famous) studies that have generally been conducted on (much) smaller version control system samples to confirm/refute their findings ... Stefano Zacchiroli Software Heritage 2021-05-19, ACES 12 / 40 Exploitation How do you query the Software Heritage archive? (on a budget) Stefano Zacchiroli Software Heritage 2021-05-19, ACES 13 / 40 Software Heritage Graph dataset Use case: large scale analyses of the most comprehensive corpus on the development history of free/open source software. Antoine Pietri, Diomidis Spinellis, Stefano Zacchiroli The Software Heritage Graph Dataset: Public software development under one roof MSR 2019: 16th Intl. Conf. on Mining Software Repositories. IEEE preprint: http://deb.li/swhmsr19 Dataset Relational representation of the full graph as a set of tables Available as open data: https://doi.org/10.5281/zenodo.2583978 Chosen as subject for the MSR 2020 Mining Challenge Formats Local use: PostgreSQL dumps, or Apache Parquet files (~1 TiB each) Live usage: Amazon Athena (SQL-queriable), Azure Data Lake Stefano Zacchiroli Software Heritage 2021-05-19, ACES 14 / 40 Sample query — most frequent first commit words 1SELECT COUNT(*)AS c,word FROM ( 2SELECT LOWER(REGEXP_EXTRACT(FROM_UTF8( 3message), '^\w+')) AS word FROM revision) 4WHERE word != '' 5GROUP BY word ORDER BY COUNT(*)DESC LIMIT 5; Count Word 71 338 310 update 64 980 346 merge 56 854 372 add 44 971 954 added 33 222 056 fix Stefano Zacchiroli Software Heritage 2021-05-19, ACES 15 / 40 Sample study — 50 years of gender differences in code contributions start from the Software Heritage graph dataset detect gender of author names using standard tooling (gender-guesser) analyze both authors and commits over time, bucketing by commit timestamp male authors 47.7% (630.2M) female authors 3.9% (51.3M) unknown 48.5% (640.6M) 1970 1980 1990 2000 2010 date 0.0% 2.0% 4.0% 6.0% 8.0% 10.0% 12.0% trend (lowess( =0.67,it=3, =0)) ratio of female authors total commits by author gender (left), ratio of active female commiters over time (right) Stefano Zacchiroli Gender Differences in Public Code Contributions: a 50-year Perspective IEEE Softw. 38(2): 45-50 (2021) Stefano Zacchiroli Software Heritage 2021-05-19, ACES 20 / 40 Discussion one can query such a corpus SQL-style but relational representation shows its limits at this scale ...at least as deployed on commercial SQL offerings such as Athena note: (naive) sharding is ineffective, due to the pseudo-random distribution of node identifiers experiments with Google BigQuery are ongoing (we broke it at the first import attempt..., due to very large arrays in directory entry tables) Stefano Zacchiroli Software Heritage 2021-05-19, ACES 21 / 40 Outline 1Software Heritage 2Querying the archive 3Graph compression 4Security synergies and outlook Stefano Zacchiroli Software Heritage 2021-05-19, ACES 22 / 40 Graph compression on the Software Heritage archive Paolo Boldi, Antoine Pietri, Sebastiano Vigna, Stefano Zacchiroli Ultra-Large-Scale Repository Analysis via Graph Compression SANER 2020, 27th Intl. Conf. on Software Analysis, Evolution and Reengineering. IEEE Research question Is it possible to efficiently perform software development history analyses at ultra large scale (= the scale of Software Heritage archive or more), on a single, relatively cheap machine? Idea Apply state-of-the-art graph compression techniques from the field of Web graph / social network analysis. Stefano Zacchiroli Software Heritage 2021-05-19, ACES 22 / 40 Background — (Web) graph compression Definition (The graph of the Web) Directed graph that has Web pages as nodes and hyperlinks between them as edges. Properties (1) Locality: pages link to pages whose URLs are lexicographically similar. URLs share long common prefixes.  use D-gap compression Adjacency lists Node Outdegree Successors ... ... ... 15 11 13,15,16,17,18,19,23,24,203,315,1034 16 10 15,16,17,22,23,24,315,316,317,3041 17 0 18 5 13,15,16,17,50 ... ... ... D-gapped adjacency lists Node Outdegree Successors ... ... ... 15 11 3,1,0,0,0,0,3,0,178,111,718 16 10 1,0,0,4,0,0,290,0,0,2723 17 0 18 5 9,1,0,0,32 ... ... ... Stefano Zacchiroli Software Heritage 2021-05-19, ACES 23 / 40 Background — (Web) graph compression (cont.) Definition (The graph of the Web) Directed graph that has Web pages as nodes and hyperlinks between them as edges. Properties (2) Similarity: pages that are close together in lexicographic order tend to have many common successors.  use reference compression Adjacency lists Node Outd. Successors ... ... ... 15 11 13,15,16,17,18,19,23,24,203,315,1034 16 10 15,16,17,22,23,24,315,316,317,3041 17 0 18 5 13,15,16,17,50 ... ... ... Copy lists Node Ref. Copy list Extra nodes ... ... ... ... 15 0 13,15,16,17,18,19,23,24,203,315,1034 16 1 01110011010 22,316,317,3041 17 18 3 11110000000 50 ... ... ... Stefano Zacchiroli Software Heritage 2021-05-19, ACES 24 / 40 Corpus Nodes Node type N. of nodes origins 88 M snapshots 57 M releases 9.9 M revisions 1.1 B directories 4.9 B contents 5.5 B Total nodes 12 B Edges Edge type N. of edges origin  snapshot 195 M snapshot  revision 616 M snapshot  release 215 M release  revision 9.9 M revision  revision 1.2 B revision  directory 1.1 B directory  directory 48 B directory  revisiony 482 M directory  content 112 B Total edges 165 B Stats for archive snapshot 2018-09-25, from the Software Heritage graph dataset. Growth rate: exponential, doubling every 22-30 months, cf.: Roberto Di Cosmo, Guillaume Rousseau, Stefano Zacchiroli Software Provenance Tracking at the Scale of Public Source Code Empirical Software Engineering 25(4): 2930-2959 (2020) Stefano Zacchiroli Software Heritage 2021-05-19, ACES 25 / 40 Graph compression pipeline MPH BV compress BFS Permute Compressed graph (forward) Transpose Compressed graph (backward) Merkle DAG MPH: minimal perfect hash, mapping Merkle IDs to 0..N-1 integers BV compress: Boldi-Vigna compression (based on MPH order) BFS: breadth-first visit to renumber Permute: update BV compression according to BFS order (Re)establishing locality key for good compression is a node ordering that ensures locality and similarity which is very much not the case with Merkle IDs, ...but is the case again after BFS reordering Stefano Zacchiroli Software Heritage 2021-05-19, ACES 26 / 40 Compression experiment Step Wall time (hours) MPH 2 BV Compress 84 BFS 19 Permute 18 Transpose 15 Total 138 (6 days) server equipped with 24 CPUs and 750 GB of RAM RAM mostly used as I/O cache for the BFS step minimum memory requirements are close to the RAM needed to load the final compressed graph in memory Stefano Zacchiroli Software Heritage 2021-05-19, ACES 27 / 40 Compression efficiency (space) Forward graph total size 91 GiB bits per edge 4.91 compression ratio 15.8% Backward graph total size 83 GiB bits per edge 4.49 compression ratio 14.4% Operating cost The structure of a full bidirectional archive graph fits in less than 200 GiB of RAM, for a hardware cost of ~300 USD. Stefano Zacchiroli Software Heritage 2021-05-19, ACES 28 / 40 Securing the open source supply chain (cont.) Software Heritage provides key ingredients for R-B pipelines: on-demand archival (e.g., of VCS commits referenced by build recipes) + long-term availability We have implemented this by integrating the GNU Guix package manager with Software Heritage https://www.softwareheritage.org/2019/04/18/ software-heritage-and-gnu-guix-join-forces-to-enable-long-term-reproducibility/ https://guix.gnu.org/blog/2019/ connecting-reproducible-deployment-to-a-long-term-source-code-archive/ Stefano Zacchiroli Software Heritage 2021-05-19, ACES 33 / 40 Tracking of vulnerable source code artifacts Software Heritage provides a unique observatory on the (best approximation of) the entire Software Commons, i.e., all software published in source code form Software provenance tracking at the scale of the world by following the transposed Software Heritage graph we can locate all known public occurrences of source code artifacts (individual source files, entier source tree, commits) in other commits or repositories we have developed two approaches to do that: 1database-based (Rousseau et al. EMSE 2020): incremental, answers a fixed set of queries, requires significant disk space 2compressed-graph-based (Boldi et al. SANER 2020): non-incremental, flexible graph-base querying, fits in RAM current applications: "intellectual property"/prior art, open source license compliance, software composition analysis (SCA)  collab. with CAST Stefano Zacchiroli Software Heritage 2021-05-19, ACES 34 / 40 Tracking of vulnerable source code artifacts (cont.) Adding in-memory commit timestamps (experimental) Idea: in-memory timestamp array (us precision, 8 bytes each), indexed by revision node id. This enables to efficiently exploit timestamp information during graph visits. Finding the earliest commit referencing a source file/dir Early experiment: finding the earliest revision containing a given file using in-memory commit timestamps, on 10 M randomly selected blobs. Mean lookup time: 4.1 ms (avg on 95% percentile: 2.2 ms) Tracking vulnerable source code files/trees Given a source file/tree affected by a known vulnerability (e.g., identified by a CVE) we can efficiently identify all commits (and repositories, extending the traversals) that reference it, triggering further inspection. Furthermore, we can efficiently select which commits to filter out during visits (e.g., "recent" ones, only in selected repos, etc.), based on timestamps of other attributes (that fit in memory or are mmap()-ed to disk). Stefano Zacchiroli Software Heritage 2021-05-19, ACES 35 / 40 Tracking of vulnerable source code artifacts (cont.) v. State-of-the-art industry offerings Similar to what GitHub/GitLab offer as a service, but: without having to rely on repository scanning, because the "big picture" is already present in the Software Heritage archive by design independent from the development platform vendor (e.g., a "vulnerable file" primarily hosted on GitHub can be spotted in GitLab repositories and vice-versa) complementary and synergistic with analyses of vulnerable dependency information (which are also available in Software Heritage via metadata mining) Caveats current granularity stops at the file level and traceability breaks with even just whitespace changes. Increasing tracking granularity to the snippet/line of code level is possible, but untested at this scale yet (cf. research roadmap) Stefano Zacchiroli Software Heritage 2021-05-19, ACES 36 / 40 A (brief) research roadmap — 1 Graph compression incremental, amortized compression  ongoing UniMi collaboration graph query languages on top of the compressed representation  LIRIS collaboration (early stages) Complex networks local topology of the global VCS graph emergent properties (the "classics": scale-free, small world, etc.) dynamic modeling of graph evolution over time  collab. with physics @ UParis Antoine Pietri, Guillaume Rousseau, Stefano Zacchiroli Determining the Intrinsic Structure of Public Software Development History MSR 2020: 17th Intl. Conf. on Mining Software Repositories. IEEE registered study protocol Stefano Zacchiroli Software Heritage 2021-05-19, ACES 37 / 40 A (brief) research roadmap — 1 Graph compression incremental, amortized compression  ongoing UniMi collaboration graph query languages on top of the compressed representation  LIRIS collaboration (early stages) Complex networks local topology of the global VCS graph emergent properties (the "classics": scale-free, small world, etc.) dynamic modeling of graph evolution over time  collab. with physics @ UParis Antoine Pietri, Guillaume Rousseau, Stefano Zacchiroli Determining the Intrinsic Structure of Public Software Development History MSR 2020: 17th Intl. Conf. on Mining Software Repositories. IEEE registered study protocol Stefano Zacchiroli Software Heritage 2021-05-19, ACES 37 / 40 A (brief) research roadmap — 2 Very-large-scale "big code" big code = apply ML/DL to source code and other development byproducts current results are language-specific and limited in scale; even the simplest problems become challenging at this scale and heterogeneity lead: scalable language detection  collaboration with UniBo lead: project classification  collaboration with CELI the VCS graph remains largely unexplored in big code lead: use GNN for VCS node classification  ANR COREOGRAPHIE Very-large-scale source code indexing common AST-based approaches for code indexing are not viable here due do maximum heterogeneity alternative: treat code as text and full-text index it previous exp.: 3-gram based indexing in Debsources, supporting regexp matching goal: find a sweet spot between the two Stefano Zacchiroli Software Heritage 2021-05-19, ACES 38 / 40 A (brief) research roadmap — 2 Very-large-scale "big code" big code = apply ML/DL to source code and other development byproducts current results are language-specific and limited in scale; even the simplest problems become challenging at this scale and heterogeneity lead: scalable language detection  collaboration with UniBo lead: project classification  collaboration with CELI the VCS graph remains largely unexplored in big code lead: use GNN for VCS node classification  ANR COREOGRAPHIE Very-large-scale source code indexing common AST-based approaches for code indexing are not viable here due do maximum heterogeneity alternative: treat code as text and full-text index it previous exp.: 3-gram based indexing in Debsources, supporting regexp matching goal: find a sweet spot between the two Stefano Zacchiroli Software Heritage 2021-05-19, ACES 38 / 40 A (brief) research roadmap — 3 Very-large-scale reproducibility in software engineering most results in empirical software engineering are determined on corpuses significantly smaller than Software Heritage  external validity threat; do results generalize to the full body of public code? 2-year research plan 1identify impactful sw. eng. studies that can be reproduced using Software Heritage selected topics (tentative): code reuse, code quality, project classification, technical debt, developer productivity 2reproduce selected studies one-by-one, at Software Heritage scale 3document findings, e.g., via RENE (REproducibility Studies and NEgative Results) scientific initiatives collaboration with Microsoft Research (just started) Stefano Zacchiroli Software Heritage 2021-05-19, ACES 39 / 40 Wrapping up Software Heritage archives all public source code as a huge Merkle DAG Querying and analyzing it at scale (20/200 B nodes/edges) is an open problem Gold mine of research leads in sw. eng., big code, reproducibility, security References (selected) Jean-François Abramatic, Roberto Di Cosmo, Stefano Zacchiroli Building the Universal Archive of Source Code Communications of the ACM, October 2018 Antoine Pietri, Diomidis Spinellis, Stefano Zacchiroli The Software Heritage graph dataset: public software development under one roof MSR 2019: 16th Intl. Conf. on Mining Software Repositories. IEEE Paolo Boldi, Antoine Pietri, Sebastiano Vigna, Stefano Zacchiroli Ultra-Large-Scale Repository Analysis via Graph Compression SANER 2020, 27th Intl. Conf. on Software Analysis, Evolution and Reengineering. IEEE Contacts Stefano Zacchiroli / upsilon.cc / [email protected] / @zacchiro Stefano Zacchiroli Software Heritage 2021-05-19, ACES 40 / 40