Soham Chakraborty

Soham Chakraborty

Auto-generated profile, based on publicly available information

Soham Chakraborty

TU Delft, Delft, Netherlands

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 June 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
HTHünkar Can Tunç
Hünkar Can Tunç
PAParosh Aziz Abdulla
Parosh Aziz Abdulla
SCSoham Chakraborty
Soham Chakraborty
SKShankaranarayanan Krishna
Shankaranarayanan Krishna
UMUmang Mathur
Umang Mathur
APAndreas Pavlogiannis
Andreas Pavlogiannis
Over the years, several memory models have been proposed to capture the subtle concurrency semantics of C/C++. One of the most fundamental problems associated with a memory model M is consistency checking: given an execution X , is X consistent with M ? This problem lies at the heart of numerous applications, including specification testing and litmus tests, stateless model checking, and dynamic analyses. As such, it has been explored extensively and its complexity is well-understood for traditional models like SC and TSO. However, less is known for the numerous model variants of C/C++, for which the problem becomes challenging due to the intricacies of their concurrency primitives. In this work we study the problem of consistency checking for popular variants of the C11 memory model, in particular, the RC 20 model, its release-acquire ( RA ) fragment, the strong and weak variants of RA ( SRA and WRA ), as well as the Relaxed fragment of RC 20. Motivated by applications in testing and model checking, we focus on reads-from consistency checking. The input is an execution X specifying a set of events, their program order and their reads-from relation, and the task is to decide the existence of a modification order on the writes of X that makes X consistent in a memory model. We draw a rich complexity landscape for this problem; our results include (i) nearly-linear-time algorithms for certain variants, which improve over prior results, (ii) fine-grained optimality results, as well as (iii) matching upper and lower bounds (NP-hardness) for other variants. To our knowledge, this is the first work to characterize the complexity of consistency checking for C11 memory models. We have implemented our algorithms inside the TruSt model checker and the C11Tester testing tool. Experiments on standard benchmarks show that our new algorithms improve consistency checking, often by a significant margin.

6 June 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
AGAndrés Goens
Andrés Goens
SCSoham Chakraborty
Soham Chakraborty
SSSusmit Sarkar
Susmit Sarkar
SASukarn Agarwal
Sukarn Agarwal
NONicolai Oswald
Nicolai Oswald
VNVijay Nagarajan
Vijay Nagarajan
Today's mobile, desktop, and server processors are heterogeneous, consisting not only of CPUs but also GPUs and other accelerators. Such heterogeneous processors are starting to expose a shared memory interface across these devices.Given that each of these individual devices typically supports a distinct instruction set architecture and a distinct memory consistency model, it is not clear what the memory consistency model of the heterogeneous machine should be. In this paper, we answer this question by formalizing "compound" memory models: we present a compositional operational model describing the resulting model when devices with distinct consistency models are fused together. We instantiate our model with the compound x86TSO/PTX model -- a CPU enforcing x86TSO and a GPU enforcing the PTX model. A key result is that the x86TSO/PTX compound model retains compiler mappings from the language-based (scoped) C memory model. This means that threads mapped to the x86TSO device can continue to use the already proven C-to-x86TSO compiler mapping, and the same for PTX.

2 January 2024 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
SCSoham Chakraborty
Soham Chakraborty
SKShankara Narayanan Krishna
Shankara Narayanan Krishna
UMUmang Mathur
Umang Mathur
APAndreas Pavlogiannis
Andreas Pavlogiannis
Weak-memory models are standard formal specifications of concurrency across hardware, programming languages, and distributed systems. A fundamental computational problem is consistency testing : is the observed execution of a concurrent program in alignment with the specification of the underlying system? The problem has been studied extensively across Sequential Consistency (SC) and weak memory, and proven to be N P -complete when some aspect of the input (e.g., number of threads/memory locations) is unbounded. This unboundedness has left a natural question open: are there efficient parameterized algorithms for testing? The main contribution of this paper is a deep hardness result for consistency testing under many popular weak-memory models: the problem remains N P -complete even in its bounded setting, where candidate executions contain a bounded number of threads, memory locations, and values. This hardness spreads across several Release-Acquire variants of C11, a popular variant of its Relaxed fragment, popular Causal Consistency models, and the POWER architecture. To our knowledge, this is the first result that fully exposes the hardness of weak-memory testing and proves that the problem admits no parameterization under standard input parameters. It also yields a computational separation of these models from SC, x86-TSO, PSO, and Relaxed, for which bounded consistency testing is either known (for SC), or shown here (for the rest), to be in polynomial time.

7 January 2025 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
EMEvgenii Moiseenko
Evgenii Moiseenko
MMMatteo Meluzzi
Matteo Meluzzi
IMInnokentii Meleshchenko
Innokentii Meleshchenko
IKIvan Kabashnyi
Ivan Kabashnyi
APAnton Podkopaev
Anton Podkopaev
SCSoham Chakraborty
Soham Chakraborty
Defining a formal model for concurrency in programming languages that addresses conflicting requirements from programmers, compilers, and architectures has been a long-standing research question. It is widely believed that traditional axiomatic per-execution models that reason about individual executions do not suffice to address these conflicting requirements. Consequently, several multi-execution models were proposed that reason about multiple executions together. Although multi-execution models were major breakthroughs in satisfying several desired properties, these models are complicated, challenging to adapt to existing language specifications given in per-execution style, and they are typically not friendly to automated reasoning tools. In response, we propose a re-execution-based memory model (XMM). Debunking the beliefs around per-execution and multi-execution models, XMM is (almost) a per-execution model. XMM reasons about individual executions, but unlike traditional per-execution models, it relates executions by a re-execution principle. As such, the memory consistency axioms and the out-of-order re-execution mechanics are orthogonal in XMM, allowing to use it as a semantic framework parameterized by a given axiomatic memory model. We instantiated the XMM framework for the RC20 language model, and proved that the resulting model XC20 provides DRF guarantees and allows standard hardware mappings and compiler optimizations. Note-worthy, XC20 is the first model of its kind that also supports thread sequentialization optimization. Moreover, XC20 is also amenable to automated reasoning. To demonstrate this, we developed a sound model checker XMC and evaluated it on several concurrency benchmarks.

13 October 2024
Verified
Conference Paper
Open access
MBMaurice Bailleu
Maurice Bailleu
DSDimitrios Stavrakakis
Dimitrios Stavrakakis
RRRodrigo Rocha
Rodrigo Rocha
SCSoham Chakraborty
Soham Chakraborty
DGDeepak Garg
Deepak Garg
PBPramod Bhatotia
Pramod Bhatotia
Modern applications employ several heterogeneous memory types for improved performance, security, and reliability. To manage them, programmers must currently digress from the traditional load/store interface and rely on various custom libraries specific to each memory type, thus introducing programmability, performance, portability, and protection challenges. To overcome these challenges, we propose Toast, a compiler-based approach that offers a simplified programming model based on the established load/store interface along with programmable error-handling and memory consistency enforcement mechanisms and a protection library for memory safety. We implement Toast in the Clang/LLVM compiler framework accompanied by a runtime library, employing software storage capabilities and hardware-based protection mechanisms. Our evaluation based on four applications, which use heterogeneous memory types, shows that Toast improves the programmability, portability, and protection of applications, while offering performance on par with a hand-optimized version of the application.

1 March 2025
Verified
Conference Paper
Open access
MFMartin Fink
Martin Fink
DSDimitrios Stavrakakis
Dimitrios Stavrakakis
DSDennis Sprokholt
Dennis Sprokholt
SCSoham Chakraborty
Soham Chakraborty
JEJan-Erik Ekberg
Jan-Erik Ekberg
PBPramod Bhatotia
Pramod Bhatotia
WebAssembly (WASM) is an immensely versatile and increasingly popular compilation target. It executes applications written in several languages (e.g., C/C++) with near-native performance in various domains (e.g., mobile, edge, cloud). Despite WASM's sandboxing feature, which isolates applications from other instances and the host platform, WASM does not inherently provide any memory safety guarantees for applications written in low-level, unsafe languages. To this end, we propose Cage, a hardware-accelerated toolchain for WASM that supports unmodified applications compiled to WASM and utilizes diverse Arm hardware features aiming to enrich the memory safety properties of WASM. Precisely, Cage leverages Arm's Memory Tagging Extension (MTE) to (i) provide spatial and temporal memory safety for heap and stack allocations and (ii) improve the performance of WASM's sandboxing mechanism. Cage further employs Arm's Pointer Authentication (PAC) to prevent leaked pointers from being reused by other WASM instances, thus enhancing WASM's security properties. We implement our system based on 64-bit WASM. We provide a WASM compiler and runtime with support for Arm's MTE and PAC. On top of that, Cage's LLVM-based compiler toolchain transforms unmodified applications to provide spatial and temporal memory safety for stack and heap allocations and prevent function pointer reuse. Our evaluation on real hardware shows that Cage incurs minimal runtime (<5.8%) and memory (<3.7%) overheads and can improve the performance of WASM's sandboxing mechanism, achieving a speedup of over 5.1%, while offering efficient memory safety guarantees.