@inproceedings{abbadini2023cage4deno,
  title        = {Cage4Deno: A Fine-Grained Sandbox for Deno Subprocesses},
  author       = {M. Abbadini and D. Facchinetti and G. Oldani and M. Rossi and S. Paraboschi},
  year         = 2023,
  booktitle    = {AsiaCCS 2023},
  publisher    = {ACM},
  address      = {Melbourne, Australia},
  url          = {https://dl.acm.org/doi/10.1145/3579856.3595799},
  note         = {Gold Open Access},
  abstract     = {Deno is a runtime for JavaScript and TypeScript that is receiving great interest by developers, and is increasingly used for the construction of back-ends of web applications. A primary goal of Deno is to provide a secure and isolated environment for the execution of JavaScript programs. It also supports the execution of subprocesses, unfortunately without providing security guarantees.}
}
@inproceedings{abbadini2023poster,
  title        = {Poster: Leveraging eBPF to enhance sandoboxing of WebAssembly runtimes},
  author       = {M. Abbadini and M. Beretta and D. Facchinetti and G. Oldani and M. Rossi and S. Paraboschi},
  year         = 2023,
  booktitle    = {AsiaCCS 2023},
  publisher    = {ACM},
  address      = {Melbourne, Australia},
  url          = {https://dl.acm.org/doi/10.1145/3579856.3592831},
  note         = {Gold Open Access},
  abstract     = {WebAssembly is a binary instruction format designed as a portable compilation target enabling the deployment of untrusted code in a safe and efficient manner. While it was originally designed to be run inside web browsers, modern runtimes like Wasmtime and WasmEdge can execute WebAssembly directly on various systems. In order to access system resources with a universal hostcall interface, a standardization effort named WebAssembly System Interface (WASI) is currently undergoing. With specific regard to the file system, runtimes must prevent hostcalls to access arbitrary locations, thus they introduce security checks to only permit access to a pre-defined list of directories. This approach not only suffers from poor granularity, it is also error-prone and has led to several security issues. In this work we replace the security checks in hostcall wrappers with eBPF programs, enabling the introduction of fine-grained per-module policies. Preliminary experiments confirm that our approach introduces limited overhead to existing runtimes.}
}
@inproceedings{abbadini2023natisand,
  title        = {NatiSand: Native Code Sandboxing for JavaScript Runtimes},
  author       = {M. Abbadini and D. Facchinetti and G. Oldani and M. Rossi and S. Paraboschi},
  year         = 2023,
  booktitle    = {RAID 2023},
  publisher    = {ACM},
  address      = {Hong Kong},
  url          = {https://dl.acm.org/doi/10.1145/3607199.3607233},
  note         = {Gold Open Access},
  abstract     = {Modern runtimes render JavaScript code in a secure and isolated environment, but when they execute binary programs and shared libraries, no isolation guarantees are provided. This is an important limitation, and it affects many popular runtimes including Node.js, Deno, and Bun. In this paper we propose NatiSand, a component for JavaScript runtimes that leverages Landlock, eBPF, and Seccomp to control the filesystem, Inter-Process Communication (IPC), and network resources available to binary programs and shared libraries. NatiSand does not require changes to the application code and offers to the user an easy interface. To demonstrate the effectiveness and efficiency of our approach we implemented NatiSand and integrated it into Deno, a modern, security-oriented JavaScript runtime. We reproduced a number of vulnerabilities affecting third-party code, showing how they are mitigated by NatiSand. We also conducted an extensive experimental evaluation to assess the performance, proving that our approach is competitive with state of the art code sandboxing solutions. The implementation is available open source.}
}
@article{vimercati2023distributed,
  title        = {Distributed query execution under access restrictions},
  author       = {Sabrina De Capitani di Vimercati and Sara Foresti and Sushil Jajodia and Giovanni Livraga and Stefano Paraboschi and Pierangela Samarati},
  year         = 2023,
  journal      = {Computers \& Security},
  volume       = 127,
  issn         = 1674048,
  url          = {https://www.sciencedirect.com/science/article/pii/S0167404822004485/pdfft?md5=87bbb554bf56f0dbf07cd0e9bb96fee1&pid=1-s2.0-S0167404822004485-main.pdf},
  note         = {Gold Open Access},
  abstract     = {The availability of a multitude of data sources has naturally increased the need for subjects to collaborate for supporting distributed computations that combine different data collections for their elaboration and analysis. Due to the quick pace at which datasets grow, often the authorities collecting and owning such datasets resort to external third parties (e.g., cloud providers) for their storage and management. Data under the control of different authorities are autonomously encrypted (using different encryption schemes and keys) for their external storage. This makes distributed computations combining these sources difficult to support. In this paper, we propose an approach enabling collaborative computations over data encrypted in storage, selectively involving also subjects that might not be authorized for accessing the data in plaintext when their collaboration is considered economically convenient. We also consider the possible adoption of trusted hardware components, to enable the evaluation of operations over plaintext data at non-fully trusted computational providers. The experimental results confirm the economic benefits that can be enabled by our proposal.}
}
@article{vimercati2023scalable,
  title        = {Scalable Distributed Data Anonymization for Large Datasets},
  author       = {Sabrina De Capitani di Vimercati and Dario Facchinetti and Sara Foresti and Giovanni Livraga and Gianluca Oldani and Stefano Paraboschi and Matthiew Rossi and Pierangela Samarati},
  year         = 2023,
  journal      = {IEEE Transactions on Big Data},
  volume       = 9,
  number       = 3,
  issn         = {2332-7790},
  url          = {https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9894678},
  note         = {Gold Open Access},
  abstract     = {k-Anonymity and ‘-diversity are two well-known privacy metrics that guarantee protection of the respondents of a dataset by obfuscating information that can disclose their identities and sensitive information. Existing solutions for enforcing them implicitly assume to operate in a centralized scenario, since they require complete visibility over the dataset to be anonymized, and can therefore have limited applicability in anonymizing large datasets. In this article, we propose a solution that extends Mondrian (an efficient and effective approach designed for achieving k-anonymity) for enforcing both k-anonymity and ‘-diversity over large datasets in a distributed manner, leveraging the parallel computation of multiple workers. Our approach efficiently distributes the computation among the workers, without requiring visibility over the dataset in its entirety. Our data partitioning limits the need for workers to exchange data, so that each worker can independently anonymize a portion of the dataset. We implemented our approach providing parallel execution on a dynamically chosen number of workers. The experimental evaluation shows that our solution provides scalability, while not affecting the quality of the resulting anonymization.}
}
@article{vimercati2023sentinels,
  title        = {Sentinels and Twins: Effective Integrity Assessment for Distributed Computation},
  author       = {Sabrina De Capitani di Vimercati and Sara Foresti and Sushil Jajodia and Stefano Paraboschi and Pierangela Samarati and Roberto Sassi},
  year         = 2023,
  journal      = {IEEE Transactions on Parallel and Distributed Systems (TPDS)},
  volume       = 34,
  number       = 1,
  issn         = 10459219,
  url          = {https://www.computer.org/csdl/api/v1/periodical/trans/td/2023/01/09925639/1HCR6US33b2/download-article/pdf},
  note         = {Gold Open Access},
  abstract     = {Distributed computing supports large scale and data-intensive computations with the cooperation of a multitude of parties, each responsible for a portion of the workload. Such parties are often not fully reliable and may return incorrect results. In this article, we address the problem of assessing the integrity of the computation results. We provide a comprehensive characterization of two techniques, sentinels and twins, evaluating their effectiveness and synergy. Sentinels are pre-computed tasks whose result is known apriori, and enable checking returned results against a ground truth. Twins are replicated tasks assigned to different workers, and enable cross-checking returned results for a same task. The analysis considers many questions that arise in the design of a concrete integrity assessment strategy and identifies the parameters that have a critical impact on the overall protection. Our model enables to tune the integrity controls so to achieve best effectiveness. The model can be applied to a variety of scenarios and offers guidelines that can find extensive application.}
}
@article{vimercati2023protecting,
  title        = {Protecting Data and Queries in Cloud-Based Scenarios},
  author       = {Sabrina De Capitani di Vimercati and Sara Foresti and Pierangela Samarati},
  year         = 2023,
  journal      = {SN Computer Science},
  volume       = 4,
  number       = 5,
  issn         = 3029743,
  url          = {https://link.springer.com/content/pdf/10.1007/s42979-023-01862-6.pdf},
  note         = {Green Open Access},
  abstract     = {Distributed computing supports large scale and data-intensive computations with the cooperation of a multitude of parties, each responsible for a portion of the workload. Such parties are often not fully reliable and may return incorrect results. In this article, we address the problem of assessing the integrity of the computation results. We provide a comprehensive characterization of two techniques, sentinels and twins, evaluating their effectiveness and synergy. Sentinels are pre-computed tasks whose result is known apriori, and enable checking returned results against a ground truth. Twins are replicated tasks assigned to different workers, and enable cross-checking returned results for a same task. The analysis considers many questions that arise in the design of a concrete integrity assessment strategy and identifies the parameters that have a critical impact on the overall protection. Our model enables to tune the integrity controls so to achieve best effectiveness. The model can be applied to a variety of scenarios and offers guidelines that can find extensive application.}
}
@article{vimercati2023supporting,
  title        = {Supporting User Protection Requirements in Cloud-Based Data Outsourcing},
  author       = {Sabrina De Capitani di Vimercati and Sara Foresti and Giovanni Livraga and Pierangela Samarati},
  year         = 2023,
  journal      = {SN Computer Science},
  volume       = 4,
  number       = 4,
  issn         = 3029743,
  url          = {https://link.springer.com/content/pdf/10.1007/s42979-023-01707-2.pdf},
  note         = {Green Open Access},
  abstract     = {The availability of cloud services ofered by diferent providers brings several advantages to users and companies, facilitating the storage, sharing, and processing of data. At the same time, the adoption of cloud services brings new security and privacy risks and challenges. As a matter of fact when leveraging cloud-based services for data storage and processing, data owners loose direct control on their data. Data and queries over them could then be at risk for both potentially improper exposure, compromising their confdentiality, or tampering, compromising their integrity. In this paper, we discuss the main issues to be addressed for guaranteeing data security and privacy in cloud-based storage and processing. We illustrate the diferent challenges to be considered and the research directions toward their solutions.}
}
@article{genovese2023dl4all,
  title        = {DL4ALL: Multi-Task Cross-Dataset Transfer Learning for Acute Lymphoblastic Leukemia Detection},
  author       = {Angelo Genovese and Vincenzo Piuri and Konstantinos N. Plataniotis and Fabio Scotti},
  year         = 2023,
  journal      = {IEEE Access},
  volume       = 11,
  issn         = {2169-3536},
  url          = {https://doi.org/10.1109/access.2023.3289219},
  note         = {Gold Open Access},
  abstract     = {Methods for the detection of Acute Lymphoblastic (or Lymphocytic) Leukemia (ALL) are increasingly considering Deep Learning (DL) due to its high accuracy in several fields, including medical imaging. In most cases, such methods use transfer learning techniques to compensate for the limited availability of labeled data. However, current methods for ALL detection use traditional transfer learning, which requires the models to be fully trained on the source domain, then fine-tuned on the target domain, with the drawback of possibly overfitting the source domain and reducing the generalization capability on the target domain. To overcome this drawback and increase the classification accuracy that can be obtained using transfer learning, in this paper we propose our method named “Deep Learning for Acute Lymphoblastic Leukemia” (DL4ALL), a novel multi-task learning DL model for ALL detection, trained using a cross-dataset transfer learning approach. The method adapts an existing model into a multi-task classification problem, then trains it using transfer learning procedures that consider both source and target databases at the same time, interleaving batches from the two domains even when they are significantly different. The proposed DL4ALL represents the first work in the literature using a multi-task cross-dataset transfer learning procedure for ALL detection. Results on a publicly-available ALL database confirm the validity of our approach, which achieves a higher accuracy in detecting ALL with respect to existing methods, even when not using manual labels for the source domain.}
}
@inproceedings{agostinello2023anomaly,
  title        = {Anomaly-Based Intrusion Detection System for DDoS with Deep Learning Techniques},
  author       = {Davide Agostinello and Angelo Genovese and Vincenzo Piuri},
  year         = 2023,
  booktitle    = {International Conference on Security and Cryptography (SECRYPT 2023)},
  publisher    = {SCITEPRESS},
  address      = {Rome, Italy},
  isbn         = {978-989-758-666-8},
  url          = {https://air.unimi.it/retrieve/47a8c370-f33d-45f6-917c-709579939361/secrypt23.pdf},
  note         = {Green Open Access},
  abstract     = {The increasing number of connected devices is fostering a rising frequency of cyber attacks, with Distributed Denial of Service (DDoS) attacks among the most common. To counteract DDoS, companies and large organizations are increasingly deploying anomaly-based Intrusion Detection Systems (IDS), which detect attack patterns by analyzing differences in malicious network traffic against a baseline of legitimate traffic. To differentiate malicious and normal traffic, methods based on artificial intelligence and, in particular, Deep Learning (DL) are being increasingly considered, due to their ability to automatically learn feature representations for the different traffic types, without need of explicit programming or handcrafted feature extraction. In this paper, we propose a novel methodology for simulating an anomaly-based IDS based on adaptive DL by designing multiple DL models working with both binary and multi—label classification on multiple datasets with different degrees of complexity. To make the DL models adaptable to different conditions, we consider adaptive architectures obtained by automatically tuning the number of neurons for each situation. Results on publicly-available datasets confirm the validity of our proposed methodology, with DL models adapting to the different conditions by increasing the number of neurons on more complex datasets and achieving the highest accuracy in the binary classification configuration.}
}
@inproceedings{locci2023explainability,
  title        = {Explainability of the Effects of Non-perturbative Data Protection in Supervised Classification},
  author       = {Stefano Locci and Luigi Di Caro and Giovanni Livraga and Marco Viviani},
  year         = 2023,
  booktitle    = {22nd IEEE/WIC International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT 2023)},
  publisher    = {IEEE},
  address      = {Venice, Italy},
  isbn         = {979-8-3503-0918-8},
  url          = {https://spdp.di.unimi.it/papers/ldlv-wiiat2023.pdf},
  note         = {Green Open Access},
  abstract     = {The increasing availability of online data has meant that data-driven models have been applied to more and more tasks in recent years. In some domains and/or applications, such data must be protected before they are used. Hence, one of the problems only partially addressed in the literature is to determine how the performance of Machine Learning models is affected by data protection. More important, the explainability of the results of such models as a consequence of data protection has been even less investigated to date. In this paper, we refer to this very problem by considering non-perturbative data protection, and by studying the explainability of supervised models applied to the data classification task.}
}
@inproceedings{livraga2023privacy,
  title        = {Unveiling the Privacy Risk: A Trade-off between User Behavior and Information Propagation in Social Media},
  author       = {Giovanni Livraga and Artjoms Olzojevs and Marco Viviani},
  year         = 2023,
  booktitle    = {12th International Conference on Complex Networks and their Applications},
  publisher    = {Springer-Verlag},
  address      = {Menton Riviera, France},
  url          = {https://spdp.di.unimi.it/papers/lov-cn2023.pdf},
  note         = {Green Open Access},
  abstract     = {The increasing availability of online data has meant that data-driven models have been applied to more and more tasks in recent years. In some domains and/or applications, such data must be protected before they are used. Hence, one of the problems only partially addressed in the literature is to determine how the performance of Machine Learning models is affected by data protection. More important, the explainability of the results of such models as a consequence of data protection has been even less investigated to date. In this paper, we refer to this very problem by considering non-perturbative data protection, and by studying the explainability of supervised models applied to the data classification task.}
}
@inproceedings{marinelli2023migration,
  title        = {Towards Migration-Free "Just-in-Case" Data Archival for Future Cloud Data Lakes Using Synthetic DNA},
  author       = {Eugenio Marinelli and Yiqing Yan and Virginie Magnone and Charlotte Dumargne and Pascal Barbry and Thomas Heinis and Raja Appuswamy},
  year         = 2023,
  booktitle    = {VLDB},
  publisher    = {PVLDB},
  address      = {Vancouver, Canada},
  volume       = 16,
  number       = 8,
  url          = {https://www.vldb.org/pvldb/vol16/p1923-marinelli.pdf},
  note         = {Green Open Access},
  abstract     = {Given the growing adoption of AI, cloud data lakes are facing the need to support cost-effective “just-in-case” data archival over long time periods to meet regulatory compliance requirements. Unfortunately, current media technologies suffer from fundamental issues that will soon, if not already, make cost-effective data archival infeasible. In this paper, we present a vision for redesigning the archival tier of cloud data lakes based on a novel, obsolescence-free storage medium–synthetic DNA. In doing so, we make two contributions: (i) we highlight the challenges in using DNA for data archival and list several open research problems, (ii) we outline OligoArchive-DSM (OA-DSM)–an end-to-end DNA storage pipeline that we are developing to demonstrate the feasibility of our vision.}
}
@article{yan2023scaling,
  title        = {Scaling logical density of DNA storage with enzymatically-ligated composite motifs},
  author       = {Yiqing Yan and Nimesh Pinnamaneni and Sachin Chalapati and Conor Crosbie and Raja Appuswamy},
  year         = 2023,
  journal      = {Scientific Reports},
  volume       = 13,
  number       = 15978,
  issn         = {2045-2322},
  url          = {https://www.nature.com/articles/s41598-023-43172-0},
  note         = {Green Open Access},
  abstract     = {DNA is a promising candidate for long-term data storage due to its high density and endurance. The key challenge in DNA storage today is the cost of synthesis. In this work, we propose composite motifs, a framework that uses a mixture of prefabricated motifs as building blocks to reduce synthesis cost by scaling logical density. To write data, we introduce Bridge Oligonucleotide Assembly, an enzymatic ligation technique for synthesizing oligos based on composite motifs. To sequence data, we introduce Direct Oligonucleotide Sequencing, a nanopore-based technique to sequence short oligos, eliminating common preparatory steps like DNA assembly, amplification and end-prep. To decode data, we introduce Motif-Search, a novel consensus caller that provides accurate reconstruction despite synthesis and sequencing errors. Using the proposed methods, we present an end-to-end experiment where we store the text “HelloWorld” at a logical density of 84 bits/cycle (14–42× improvement over state-of-the-art).}
}
@inproceedings{carraro2023performance,
  title        = {Performance and Energy Savings Trade-Off with Uncertainty-Aware Cloud Workload Forecasting},
  author       = {Diego Carraro and Andrea Rossi and Andrea Visentin and Steven Prestwich and Kenneth N. Brown},
  year         = 2023,
  booktitle    = {IEEE ICNP'23 - The 31st IEEE International Conference on Network Protocols, CLOUD-EDGE CONTINUUM (CEC) Workshop 2023},
  publisher    = {IEEE},
  address      = {Reykjavik, Iceland},
  url          = {https://cora.ucc.ie/items/3bc19eda-3313-49d6-aa6c-e5a9c6b30e8b},
  note         = {Green Open Access},
  abstract     = {Cloud managers typically leverage future workload predictions to make informed decisions on resource allocation, where the ultimate goal of the allocation is to meet customers’ demands while reducing the provisioning cost. Among several workload forecasting approaches proposed in the literature, uncertainty-aware time series analysis solutions are desirable in cloud scenarios because they can predict the distribution of future demand and provide bounds associated with a given service level set by the resource manager. The effectiveness of uncertainty-based workload predictions is normally assessed in terms of accuracy metrics (e.g. MAE) and service level (e.g. Success Rate), but the effect on the resource provisioning cost is under investigated. We propose an evaluation framework to assess the impact of uncertainty-aware predictions on the performance vs cost trade-off, where we express the cost in terms of energy savings. We illustrate the framework’s effectiveness by simulating two real-world cloud scenarios where an optimizer leverages workload predictions to allocate resources to satisfy a desired service level while minimizing energy waste. Offline experiments compare representative uncertainty-aware models and a new model (HBNN++) that we propose, which predict a cluster trace’s GPU demand. We show that more effective uncertainty modelling can save energy without violating desired service level targets and that model performance varies depending on the specific details of the allocation scheme, server and GPU energy costs.}
}
@inproceedings{rossi2023clustering,
  title        = {Clustering-Based Numerosity Reduction for Cloud Workload Forecasting},
  author       = {Andrea Rossi and Andrea Visentin and Steven Prestwich and Kenneth N. Brown},
  year         = 2023,
  booktitle    = {Algorithmic Aspects of Cloud Computing: 8th International Symposium, ALGOCLOUD 2023},
  publisher    = {Springer Verlag},
  address      = {Amsterdam, Netherlands},
  url          = {https://link.springer.com/chapter/10.1007/978-3-031-49361-4_7},
  note         = {Green Open Access},
  abstract     = {Finding smaller versions of large datasets that preserve the same characteristics as the original ones is becoming a central problem in Machine Learning, especially when computational resources are limited, and there is a need to reduce energy consumption. In this paper, we apply clustering techniques for wisely selecting a subset of datasets for training models for time series prediction of future workload in cloud computing. We train Bayesian Neural Networks (BNNs) and state-of-the-art probabilistic models to predict machine-level future resource demand distribution and evaluate them on unseen data from virtual machines in the Google Cloud data centre. Experiments show that selecting the training data via clustering approaches such as Self Organising Maps allows the model to achieve the same accuracy in less than half the time, requiring less than half the datasets rather than selecting more data at random. Moreover, BNNs can capture uncertainty aspects that can better inform scheduling decisions, which state-of-the-art time series forecasting methods cannot do. All the considered models achieve prediction time performance suitable for real-world scenarios.}
}
@inproceedings{abbadini2023lightweight,
  title        = {Lightweight Cloud Application Sandboxing},
  author       = {Marco Abbadini and Michele Beretta and Dario Facchinetti and Gianluca Oldani and Matthew Rossi and Stefano Paraboschi},
  year         = 2023,
  booktitle    = {14th IEEE International Conference on Cloud Computing Technology and Science (CLOUDCOM), December 4-6, 2023},
  publisher    = {IEEE},
  address      = {Naples, Italy},
  url          = {https://cs.unibg.it/seclab-papers/2023/CLOUDCOM/dmng.pdf},
  note         = {Green Open Access},
  abstract     = {Modern cloud applications can quickly grow to an elaborate and intricate tangle of services. In this scenario, paying attention to security aspects is important to mitigate the impact of incidents. Indeed, several research works and industrial standards recommend the integration of least privilege policies to prevent disruptions such as file system tampering. Unfortunately, technologies like containers virtualize file system resources with a volume-based approach, which may be overly coarse. In this work we address this problem proposing an approach that restrict application access to file system resources with a resource-based granularity. To this end, we develop a flexible and intuitive tool that relies on instrumentation to collect, merge, and audit the activity traces generated by any application component. We then demonstrate how this information is used to create fine-grained access policies, and introduce sandboxing using recent kernel security modules, strengthening the security boundary of the whole application. In the experimental evaluation we showcase the mitigation capabilities associated with our approach, and the low performance footprint. The proposal is associated with an open source implementation.}
}
@inproceedings{blach2024high,
  title        = {A High-Performance Design, Implementation, Deployment, and Evaluation of the Slim Fly Network},
  author       = {Nils Blach and Maciej Besta and Daniele De Sensi and Jens Domke and Hussein Harake and Shigang Li and Patrick Iff and Marek Konieczny and Kartik Lakhotia and Ales Kubicek and Marcel Ferrari and Fabrizio Petrini and Torsten Hoefler},
  year         = 2024,
  booktitle    = {21st USENIX Symposium on Networked Systems Design and Implementation (NSDI ‘24), April 16–18, 2024},
  publisher    = {USENIX Association},
  address      = {Santa Clara, CA, USA},
  isbn         = {978-1-939133-39-7},
  url          = {https://www.usenix.org/conference/nsdi24/presentation/blach},
  note         = {Green Open Access},
  abstract     = {Novel low-diameter network topologies such as Slim Fly (SF) offer significant cost and power advantages over the established Fat Tree, Clos, or Dragonfly. To spearhead the adoption of low-diameter networks, we design, implement, deploy, and evaluate the first real-world SF installation. We focus on deployment, management, and operational aspects of our test cluster with 200 servers and carefully analyze performance. We demonstrate techniques for simple cabling and cabling validation as well as a novel high-performance routing architecture for InfiniBand-based low-diameter topologies. Our real-world benchmarks show SF's strong performance for many modern workloads such as deep neural network training, graph analytics, or linear algebra kernels. SF outperforms non-blocking Fat Trees in scalability while offering comparable or better performance and lower cost for large network sizes. Our work can facilitate deploying SF while the associated (open-source) routing architecture is fully portable and applicable to accelerate any low-diameter interconnect.}
}
@article{besta2024graph,
  title        = {Graph of Thoughts: Solving Elaborate Problems with Large Language Models},
  author       = {Besta, Maciej and Blach, Nils and Kubicek, Ales and Gerstenberger, Robert and Podstawski, Michał and Gianinazzi, Lukas and Gajda, Joanna and Lehmann, Tomasz and Niewiadomski, Hubert and Nyczyk, Piotr and Hoefler, Torsten},
  year         = 2024,
  journal      = {Proceedings of the AAAI Conference on Artificial Intelligence (AAAI ‘24)},
  publisher    = {Association for the Advancement of Artificial Intelligence},
  address      = {Vancouver, Canada},
  volume       = 38,
  number       = 16,
  pages        = {},
  doi          = {10.1609/aaai.v38i16.29720},
  abstract     = {We introduce Graph of Thoughts (GoT): a framework that advances prompting capabilities in large language models (LLMs) beyond those offered by paradigms such as Chain-of-Thought or Tree of Thoughts (ToT). The key idea and primary advantage of GoT is the ability to model the information generated by an LLM as an arbitrary graph, where units of information (""LLM thoughts"") are vertices, and edges correspond to dependencies between these vertices. This approach enables combining arbitrary LLM thoughts into synergistic outcomes, distilling the essence of whole networks of thoughts, or enhancing thoughts using feedback loops. We illustrate that GoT offers advantages over state of the art on different tasks, for example increasing the quality of sorting by 62% over ToT, while simultaneously reducing costs by >31%. We ensure that GoT is extensible with new thought transformations and thus can be used to spearhead new prompting schemes. This work brings the LLM reasoning closer to human thinking or brain mechanisms such as recurrence, both of which form complex networks.}
}
@inproceedings{gianinazzi2024arrow,
  title        = {Arrow Matrix Decomposition: A Novel Approach for Communication-Efficient Sparse Matrix Multiplication},
  author       = {Gianinazzi, Lukas and Ziogas, Alexandros Nikolaos and Huang, Langwen and Luczynski, Piotr and Ashkboos, Saleh and Scheidl, Florian and Carigiet, Armon and Ge, Chio and Abubaker, Nabil and Besta, Maciej and Ben-Nun, Tal and Hoefler, Torsten},
  year         = 2024,
  booktitle    = {Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PpoPP ‘24)},
  publisher    = {ACM},
  address      = {Edinburgh, United Kingdom},
  doi          = {10.1145/3627535.3638496},
  abstract     = {We propose a novel approach to iterated sparse matrix dense matrix multiplication, a fundamental computational kernel in scientific computing and graph neural network training. In cases where matrix sizes exceed the memory of a single compute node, data transfer becomes a bottleneck. An approach based on dense matrix multiplication algorithms leads to sub-optimal scalability and fails to exploit the sparsity in the problem. To address these challenges, we propose decomposing the sparse matrix into a small number of highly structured matrices called arrow matrices, which are connected by permutations. Our approach enables communication-avoiding multiplications, achieving a polynomial reduction in communication volume per iteration for matrices corresponding to planar graphs and other minor-excluded families of graphs. Our evaluation demonstrates that our approach outperforms a state-of-the-art method for sparse matrix multiplication on matrices with hundreds of millions of rows, offering near-linear strong and weak scaling.}
}
@article{besta2024demystifying,
  title        = {Demystifying Chains, Trees, and Graphs of Thoughts},
  author       = {Besta, Maciej and Memedi, Florim and Zhang, Zhenyu and Gerstenberger, Robert and Piao, Guangyuan and Blach, Nils and Nyczyk, Piotr and Copik, Marcin and Kwaśniewski, Grzegorz and Müller, Jürgen and Gianinazzi, Lukas and Kubicek, Ales and Niewiadomski, Hubert and O’Mahony, Aidan and Mutlu, Onur and Hoefler, Torsten},
  year         = 2024,
  journal      = {arXiv},
  publisher    = {Cornell University},
  address      = {Ithaca, NY, USA},
  url          = {http://arxiv.org/abs/2401.14295},
  abstract     = {The field of natural language processing (NLP) has witnessed significant progress in recent years, with a notable focus on improving large language models' (LLM) performance through innovative prompting techniques. Among these, prompt engineering coupled with structures has emerged as a promising paradigm, with designs such as Chain-of-Thought, Tree of Thoughts, or Graph of Thoughts, in which the overall LLM reasoning is guided by a structure such as a graph. As illustrated with numerous examples, this paradigm significantly enhances the LLM's capability to solve numerous tasks, ranging from logical or mathematical reasoning to planning or creative writing. To facilitate the understanding of this growing field and pave the way for future developments, we devise a general blueprint for effective and efficient LLM reasoning schemes. For this, we conduct an in-depth analysis of the prompt execution pipeline, clarifying and clearly defining different concepts. We then build the first taxonomy of structure-enhanced LLM reasoning schemes. We focus on identifying fundamental classes of harnessed structures, and we analyze the representations of these structures, algorithms executed with these structures, and many others. We refer to these structures as reasoning topologies, because their representation becomes to a degree spatial, as they are contained within the LLM context. Our study compares existing prompting schemes using the proposed taxonomy, discussing how certain design choices lead to different patterns in performance and cost. We also outline theoretical underpinnings, relationships between prompting and other parts of the LLM ecosystem such as knowledge bases, and the associated research challenges. Our work will help to advance future prompt engineering techniques.}
}
@inproceedings{besta2023high,
  title        = {High-Performance and Programmable Attentional Graph Neural Networks with Global Tensor Formulations},
  author       = {Besta, Maciej and Renc, Pawel and Gerstenberger, Robert and Sylos Labini, Paolo and Ziogas, Alexandros and Chen, Tiancheng and Gianinazzi, Lukas and Scheidl, Florian and Szenes, Kalman and Carigiet, Armon and Iff, Patrick and Kwaśniewski, Grzegorz and Kanakagiri, Raghavendra and Ge, Chio and Jaeger, Sammy and Wąs, Jarosław and Vella, Flavio and Hoefler, Torsten},
  year         = 2023,
  booktitle    = {Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ‘23)},
  publisher    = {ACM},
  address      = {Denver, CO, USA},
  doi          = {10.1145/3581784.3607067},
  abstract     = {Graph attention models (A-GNNs), a type of Graph Neural Networks (GNNs), have been shown to be more powerful than simpler convolutional GNNs (C-GNNs). However, A-GNNs are more complex to program and difficult to scale. To address this, we develop a novel mathematical formulation, based on tensors that group all the feature vectors, targeting both training and inference of A-GNNs. The formulation enables straightforward adoption of communication-minimizing routines, it fosters optimizations such as vectorization, and it enables seamless integration with established linear algebra DSLs or libraries such as GraphBLAS. Our implementation uses a data redistribution scheme explicitly developed for sparse-dense tensor operations used heavily in GNNs, and fusing optimizations that further minimize memory usage and communication cost. We ensure theoretical asymptotic reductions in communicated data compared to the established message-passing GNN paradigm. Finally, we provide excellent scalability and speedups of even 4--5x over modern libraries such as Deep Graph Library.}
}
@inproceedings{besta2023graph,
  title        = {The Graph Database Interface: Scaling Online Transactional and Analytical Graph Workloads to Hundreds of Thousands of Cores},
  author       = {Besta, Maciej and Gerstenberger, Robert and Fischer, Marc and Podstawski, Michal and Blach, Nils and Egeli, Berke and Mitenkov, Georgy and Chlapek, Wojciech and Michalewicz, Marek and Niewiadomski, Hubert and Müller, Jürgen and Hoefler, Torsten},
  year         = 2023,
  booktitle    = {Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ‘23)},
  publisher    = {ACM},
  address      = {Denver, CO, USA},
  doi          = {10.1145/3581784.3607068},
  abstract     = {Graph databases (GDBs) are crucial in academic and industry applications. The key challenges in developing GDBs are achieving high performance, scalability, programmability, and portability. To tackle these challenges, we harness established practices from the HPC landscape to build a system that outperforms all past GDBs presented in the literature by orders of magnitude, for both OLTP and OLAP workloads. For this, we first identify and crystallize performance-critical building blocks in the GDB design, and abstract them into a portable and programmable API specification, called the Graph Database Interface (GDI), inspired by the best practices of MPI. We then use GDI to design a GDB for distributed-memory RDMA architectures. Our implementation harnesses one-sided RDMA communication and collective operations, and it offers architecture-independent theoretical performance guarantees. The resulting design achieves extreme scales of more than a hundred thousand cores. Our work will facilitate the development of next-generation extreme-scale graph databases.}
}
@inproceedings{besta2023hot,
  title        = {HOT: Higher-Order Dynamic Graph Representation Learning with Efficient Transformers},
  author       = {Besta, Maciej and Catarino, Afonso Claudino and Gianinazzi, Lukas and Blach, Nils and Nyczyk, Piotr and Niewiadomski, Hubert and Hoefler, Torsten},
  year         = 2023,
  booktitle    = {Proceedings of the Second Learning on Graphs Conference (LoG ‘23)},
  publisher    = {PMLR},
  address      = {Virtual},
  volume       = 231,
  url          = {https://proceedings.mlr.press/v231/besta24a/besta24a.pdf},
  abstract     = {Many graph representation learning (GRL) problems are dynamic, with millions of edges added or removed per second. A fundamental workload in this setting is dynamic link prediction: using a history of graph updates to predict whether a given pair of vertices will become connected. Recent schemes for link prediction in such dynamic settings employ Transformers, modeling individual graph updates as single tokens. In this work, we propose HOT: a model that enhances this line of works by harnessing higher-order (HO) graph structures; specifically, k-hop neighbors and more general subgraphs containing a given pair of vertices. Harnessing such HO structures by encoding them into the attention matrix of the underlying Transformer results in higher accuracy of link prediction outcomes, but at the expense of increased memory pressure. To alleviate this, we resort to a recent class of schemes that impose hierarchy on the attention matrix, significantly reducing memory footprint. The final design offers a sweetspot between high accuracy and low memory utilization. HOT outperforms other dynamic GRL schemes, for example achieving 9%, 7%, and 15% higher accuracy than – respectively – DyGFormer, TGN, and GraphMixer, for the MOOC dataset. Our design can be seamlessly extended towards other dynamic GRL workloads.}
}
@article{iff2023rapidchiplet,
  title        = {RapidChiplet: A Toolchain for Rapid Design Space Exploration of Chiplet Architectures},
  author       = {Iff, Patrick and Bruggmann, Benigna and Besta, Maciej and Benini, Luca and Hoefler, Torsten},
  year         = 2023,
  journal      = {arXiv},
  publisher    = {Cornell University},
  address      = {Ithaca, NY, USA},
  url          = {http://arxiv.org/abs/2311.06081},
  abstract     = {Chiplet architectures are a promising paradigm to overcome the scaling challenges of monolithic chips. Chiplets offer heterogeneity, modularity, and cost-effectiveness. The design space of chiplet architectures is huge as there are many degrees of freedom such as the number, size and placement of chiplets, the topology of the inter-chiplet interconnect and many more. Existing tools for cost and performance prediction are often too slow to explore this design space. We present RapidChiplet, a fast, open-source toolchain to predict latency and throughput of the inter-chiplet interconnect, as well as a chip's manufacturing cost and thermal stability.}
}
@article{besta2023demystifying,
  title        = {Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries},
  author       = {Besta, Maciej and Gerstenberger, Robert and Peter, Emanuel and Fischer, Marc and Podstawski, Michał and Barthels, Claude and Alonso, Gustavo and Hoefler, Torsten},
  year         = 2023,
  journal      = {ACM Computing Surveys},
  publisher    = {ACM},
  volume       = 56,
  number       = 2,
  doi          = {10.1145/3604932},
  issn         = {0360-0300},
  abstract     = {Numerous irregular graph datasets, for example social networks or web graphs, may contain even trillions of edges. Often, their structure changes over time and they have domain-specific rich data associated with vertices and edges. Graph database systems such as Neo4j enable storing, processing, and analyzing such large, evolving, and rich datasets. Due to the sheer size and irregularity of such datasets, these systems face unique design challenges. To facilitate the understanding of this emerging domain, we present the first survey and taxonomy of graph database systems. We focus on identifying and analyzing fundamental categories of these systems (e.g., document stores, tuple stores, native graph database systems, or object-oriented systems), the associated graph models (e.g., Resource Description Framework or Labeled Property Graph), data organization techniques (e.g., storing graph data in indexing structures or dividing data into records), and different aspects of data distribution and query execution (e.g., support for sharding and Atomicity, Consistency, Isolation, Durability). Fifty-one graph database systems are presented and compared, including Neo4j, OrientDB, and Virtuoso. We outline graph database queries and relationships with associated domains (NoSQL stores, graph streaming, and dynamic graph algorithms). Finally, we outline future research and engineering challenges related to graph databases.}
}
@article{iff2023cached,
  title        = {Cached Operator Reordering: A Unified View for Fast GNN Training},
  author       = {Iff, Julia and Ivanov, Andrei and Ben-Nun, Tal and Dryden, Nikoli and Besta, Maciej and Shen, Siyuan and Hoefler, Torsten},
  year         = 2023,
  journal      = {arXiv},
  publisher    = {Cornell University},
  address      = {Ithaca, NY, USA},
  url          = {https://arxiv.org/abs/2308.12093},
  abstract     = {Graph Neural Networks (GNNs) are a powerful tool for handling structured graph data and addressing tasks such as node classification, graph classification, and clustering. However, the sparse nature of GNN computation poses new challenges for performance optimization compared to traditional deep neural networks. We address these challenges by providing a unified view of GNN computation, I/O, and memory. By analyzing the computational graphs of the Graph Convolutional Network (GCN) and Graph Attention (GAT) layers -- two widely used GNN layers -- we propose alternative computation strategies. We present adaptive operator reordering with caching, which achieves a speedup of up to 2.43x for GCN compared to the current state-of-the-art. Furthermore, an exploration of different caching schemes for GAT yields a speedup of up to 1.94x. The proposed optimizations save memory, are easily implemented across various hardware platforms, and have the potential to alleviate performance bottlenecks in training large-scale GNN models.}
}
@inproceedings{iff2023sparse,
  title        = {Sparse Hamming Graph: A Customizable Network-on-Chip Topology},
  author       = {Iff, Patrick and Besta, Maciej and Cavalcante, Matheus and Fischer, Tim and Benini, Luca and Hoefler, Torsten},
  year         = 2023,
  booktitle    = {Proceedings of the 60th Annual ACM/IEEE Design Automation Conference (DAC ‘23)},
  publisher    = {IEEE},
  address      = {San Francisco, CA, USA},
  doi          = {10.1109/DAC56929.2023.10247754},
  abstract     = {Chips with hundreds to thousands of cores require scalable networks-on-chip (NoCs). Customization of the NoC topology is necessary to reach the diverse design goals of different chips. We introduce sparse Hamming graph, a novel NoC topology with an adjustable cost-performance trade-off that is based on four NoC topology design principles we identified. To efficiently customize this topology, we develop a toolchain that leverages approximate floorplanning and link routing to deliver fast and accurate cost and performance predictions. We demonstrate how to use our methodology to achieve desired cost-performance trade-offs while outperforming established topologies in cost, performance, or both.}
}
@inproceedings{iff2023hexamesh,
  title        = {HexaMesh: Scaling to Hundreds of Chiplets with an Optimized Chiplet Arrangement},
  author       = {Iff, Patrick and Besta, Maciej and Cavalcante, Matheus and Fischer, Tim and Benini, Luca and Hoefler, Torsten},
  year         = 2023,
  booktitle    = {Proceedings of the 60th Annual ACM/IEEE Design Automation Conference (DAC ‘23)},
  publisher    = {IEEE},
  address      = {San Francisco, CA, USA},
  doi          = {10.1109/DAC56929.2023.10248006},
  abstract     = {2.5D integration is an important technique to tackle the growing cost of manufacturing chips in advanced technology nodes. This poses the challenge of providing high-performance inter-chiplet interconnects (ICIs). As the number of chiplets grows to tens or hundreds, it becomes infeasible to hand-optimize their arrangement in a way that maximizes the ICI performance. In this paper, we propose HexaMesh, an arrangement of chiplets that outperforms a grid arrangement both in theory (network diameter reduced by 42%; bisection bandwidth improved by 130%) and in practice (latency reduced by 19%; throughput improved by 34%). MexaMesh enables large-scale chiplet designs with high-performance ICIs.}
}
@article{besta2023parallel,
  title        = {Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis},
  author       = {Besta, Maciej and Hoefler, Torsten},
  year         = 2023,
  journal      = {IEEE TPAMI},
  publisher    = {IEEE},
  volume       = 46,
  doi          = {10.1109/TPAMI.2023.3303431},
  abstract     = {Graph neural networks (GNNs) are among the most powerful tools in deep learning. They routinely solve complex problems on unstructured networks, such as node classification, graph classification, or link prediction, with high accuracy. However, both inference and training of GNNs are complex, and they uniquely combine the features of irregular graph processing with dense and regular computations. This complexity makes it very challenging to execute GNNs efficiently on modern massively parallel architectures. To alleviate this, we first design a taxonomy of parallelism in GNNs, considering data and model parallelism, and different forms of pipelining. Then, we use this taxonomy to investigate the amount of parallelism in numerous GNN models, GNN-driven machine learning tasks, software frameworks, or hardware accelerators. We use the work-depth model, and we also assess communication volume and synchronization. We specifically focus on the sparsity/density of the associated tensors, in order to understand how to effectively apply techniques such as vectorization. We also formally analyze GNN pipelining, and we generalize the established Message-Passing class of GNN models to cover arbitrary pipeline depths, facilitating future optimizations. Finally, we investigate different forms of asynchronicity, navigating the path for future asynchronous parallel GNN pipelines. The outcomes of our analysis are synthesized in a set of insights that help to maximize GNN performance, and a comprehensive list of challenges and opportunities for further research into efficient GNN computations. Our work will help to advance the design of future GNNs.}
}