I recently attended the AI Engineer Code Summit in New York, an invite-only gathering of AI leaders and engineers. One theme emerged repeatedly in conversations with attendees building with AI: the belief that we’re approaching a future where developers will never need to look at code again. When I pressed these proponents, several made a similar argument:

Forty years ago, when high-level programming languages like C became increasingly popular, some of the old guard resisted because C gave you less control than assembly. The same thing is happening now with LLMs.

On its face, this analogy seems reasonable. Both represent increasing abstraction. Both initially met resistance. Both eventually transformed how we write software. But this analogy really thrashes my cache because it misses a fundamental distinction that matters more than abstraction level: determinism.

The difference between compilers and LLMs isn’t just about control or abstraction. It’s about semantic guarantees. And as I’ll argue, that difference has profound implications for the security and correctness of software.

As I wrote back in 2017 in “Automation of Automation,” there are fundamental limits on what we can automate. But those limits don’t eliminate determinism in the tools we’ve built; they simply mean we can’t automatically prove every program correct. Compilers don’t try to prove your program correct; they just faithfully translate it.

This is an excerpt from the Trail of Bits blog. You can read the full post here.

It all began, as many great adventures do, at Empire Hacking. There, I encountered the inimitable @ImmigrantJackson, a YouTuber with a penchant for public transit and a dream: to break the world record for visiting every subway stop in New York City in the least time possible. (And, of course, to film the journey, what for those delicious likes, comments, and subscriptions.)

The only problem was: Immigrant Jackson didn’t know the fastest route. Surrounded by a room full of Trail of Bits computer scientists, he figured he’d ask our advice. The rules were simple. He didn’t need to exit the subway car; simply passing through a stop, even on an express train, counted as a “visit.” Stops could be visited multiple times, although this would of course be suboptimal. And there was no need to visit Staten Island … because we’re civilized. We live in a society. So, where should he start, and what would be the best route?

The coterie of curious computer coders coalescing around the inquisitor quickly classified this question as a case of the Traveling Salesman Problem (TSP). TSP is a classical problem in computer science in which one must find the shortest route for a traveling salesman to visit each city on a map. TSP is known to be computationally intractable to solve optimally for networks even as small as the New York subway system. Therefore, everyone dismissed the problem as “impossible.”

Except for me.

You see, my now-ancient PhD dissertation was on combinatorial optimization and approximation algorithms: tools for solving problems like TSP efficiently with a result that is not necessarily optimal, but at least close to optimal. I knew that there were algorithms capable of solving TSP very quickly, producing a route guaranteed to be at most 50% longer than the optimal solution. In fact, one of the results of my dissertation was the surprising revelation that even if you choose a feasible route at random, it will, on average, be only thrice the length of the optimal solution.

This, dear reader, was how I was nerd-sniped into optimizing (speedrunning?) the NYC subway.

The first challenge was that, even when you discard Staten Italy, the subway system still has a lot of stations. There are close to 500. This exercise was fun and all, but I wasn’t about to spend hours encoding hundreds of stations, lines, transfer points, headways, and average trip times into a program.

There is an open standard for specifying public transit data: the General Transit Feed Specification (GTFS). Fortunately, the MTA has a public API implementing GTFS. It’s just a collection of CSV files that are quite straightforward to parse. The dataset is sufficient to construct a graph with a node for each subway station and an edge if there is a subway line that connects the two stations. Actually, the data represents subway platforms rather than stations, which is necessary to calculate things like transfer times between train lines.

The New York Subway network is a directed graph: some neighboring stations are accessible to each other only in one direction. For example, the Aqueduct Racetrack station only has a platform for northbound trains, not southbound trains. The best algorithms for approximating a solution to TSP on directed graphs are not great, only guaranteeing a solution of three or four times the length of the optimal solution. Therefore, I decided to relax the problem to an undirected graph (i.e., I assume that every station has trains to its neighbors bidirectionally). This turned out not to be an issue and permitted the use of the Christofides algorithm, which guarantees a solution at most 50% longer than optimal.

The next and final relaxation is to partially ignore actual timetables and headways. When a transfer between lines is necessary, I assume that the transfer will require the “minimum transfer time” reported by GTFS (i.e., the amount of time required to walk from one platform to another) plus one-half the average headway for that line throughout the day. Therefore, the resulting route has the potential to strand the poor YouTuber on the last train at the end of a line. Validating the resulting route’s real-world feasibility is left as an exercise to the reader.

The Christofides algorithm was able to approximate a solution to the TSP for my relaxed subway network graph in a matter of milliseconds. This is compared to the unfathomable amount of computation required to brute-force calculate the optimal solution, an amount so large that it afforded me the horrifying opportunity to learn that there is a whole community of “googologists” who compete with each other to name large numbers. We’re talking googolchime levels of computation. Guppybell levels, even!

The resulting tour visits all 474 stations, 155 of which are visited more than once. The tour requires 34 transfers. The expected time for completing this tour is 20 hours, 42 minutes. That’s about 45 minutes faster than the record, which was about 21 and a half hours.

This is neat and all, but we spent an unnecessary amount of energy encoding the New York subway system as a graph. What else might we do with it? One straightforward computation is to calculate each station’s eigenvector centrality. Imagine you’re given the Sisyphean task of riding the subway for all eternity. Every time you arrive at a station, you flip a coin. If it’s heads, you stay on the current train. If it’s tails, you get off and transfer to another line or direction. If you were to pause your infinite tour at any arbitrary point in time, what’s the probability that you are at a particular station? The higher the probability, the more “centrally connected” the station. That’s exactly what eigenvector centrality calculates.

Eigenvector centrality is actually what Google originally used in its PageRank algorithm to rank the relative importance (centrality) of web pages. Each page is like a subway station, and hyperlinks on the page are like the subway lines connecting them. Eigenvector centrality is relatively easy to calculate, either directly (it’s related to the eigenspectrum of the graph’s adjacency matrix, thanks to spooky spectral graph theory magic) or using a technique called power iteration (which relies on a convergence that happens when you multiply the adjacency matrix by a vector a bunch of times). Either way, you can calculate it with a single function call in NetworkX.

What do you think will be the most probable stop on your infinite subway tour? Or, another way to ask the same question: Which stop will you visit most often on your tour? Unsurprisingly, it will be Times Square, with a probability of a little over 30%. The next most probable station is 42nd St. Port Authority Bus Terminal, coming in at about 8%. Then 50th St., 59th St. Columbus Circle, Grand Central 42nd St., and 34th St. Penn Station are all between 4% and 5%.

So, what have we learned? First of all, don’t attend Empire Hacking without the expectation of being intellectually stimulated. Secondly, don’t immediately discount a problem just because it is NP-hard or computationally intractable to solve; you might be able to approximate a solution of sufficient optimality. Thirdly, Times Square may not be the “center of the universe,” but it is definitely the center of the New York subway system. Finally, remember to like, comment, and subscribe!

This is an excerpt from the Trail of Bits blog. You can read the full post here.

Earlier this month, the maintainer of Cheating-Daddy discovered that a Y-Combinator-funded startup had copied their GPL-licensed codebase, stripped out the comments, and re-released it as “Glass” under an incompatible license. This isn’t an isolated incident; we see code theft and improper vendoring constantly during security assessments. So we built a tool to catch it automatically.

Vendetect is our new open-source tool for detecting copied and vendored code between repositories. It uses semantic fingerprinting to identify similar code even when variable names change or comments disappear. More importantly, unlike academic plagiarism detectors, it understands version control history, helping you trace vendored code back to its exact source commit.

This is an excerpt from the Trail of Bits blog. You can read the full post here.

Have you ever tried compiling a piece of open-source software, only to discover that you neglected to install one of its native dependencies? Or maybe a binary “fell off the back of a truck” and you want to try running it but have no idea what shared libraries it needs. Or maybe you need to use a poorly packaged piece of software whose maintainers neglected to list a native dependency.

Deptective, our new open-source tool, solves these problems. You can give it any program, script, or command, and it will find a set of packages sufficient to run the software successfully.

This is an excerpt from the Trail of Bits blog. You can read the full post here.

This blog post highlights key points from our new white paper Preventing Account Takeovers on Centralized Cryptocurrency Exchanges, which documents ATO-related attack vectors and defenses tailored to CEXes.

Imagine trying to log in to your centralized cryptocurrency exchange (CEX) account and your password and username just… don’t work. You try them again. Same problem. Your heart rate increases a little bit at this point, especially since you are using a password manager. Maybe a service outage is all that’s responsible (knock on wood), and your password will work again as soon as it’s fixed? But it is becoming increasingly likely that you’re the victim of an account takeover (ATO).

CEXes’ choices dictate how (or if) the people who use them can secure their funds. Since account security features vary between platforms and are not always documented, the user might not know what to expect nor how to configure their account best for their personal threat model. Design choices like not supporting phishing-resistant multifactor authentication (MFA) methods like U2F hardware security keys, or not tracking user events in order to push in-app “was this you?” account lockdown prompts when anomalies happen invite the attacker in.

Our white paper’s goal is to inform and enable CEXes to provide a secure-by-design platform for their users. Executives can get a high-level overview of the vulnerabilities and entities involved in user account takeover. We recommend a set of overlapping security controls that they can bring to team leads and technical product managers to check for and prioritize if not yet implemented. Security engineers and software engineers can also use our work as a reference for the risks of not integrating, maintaining, and documenting appropriate ATO mitigations.

This is an excerpt from the Trail of Bits blog. You can read the full post here.

I grew up on the fringes of suburbia, at the cusp of what most would consider rural Pennsylvania. In the Spring, we gagged from the stench of manure. In the Fall, Schools closed on the first day of hunting season. In the Winter, fresh, out-of-season fruits were missing from the grocer. All year round, procuring exotic ingredients like avocados entailed a forty-five-minute drive toward civilization. During the school year, I was the first to be picked up and last to be dropped off by the bus, enduring a ride that was well over an hour each way.

I also grew up in tandem with the burgeoning cruise line industry. My parents quickly adopted that mode of travel, and it eventually became our sole form of vacation. As a kid, it was great: I had the freedom to roam the decks on my own, there were innumerable activities, and an unlimited supply of delicious foods with exotic names like “Consommé Madrilene” and “Contrefilet of Prime Beef Périgueux”. My parents loved it because it kept their kids busy, was very affordable (relative to equivalent landed resorts), and had sufficient calories to satisfy their growing boy’s voracious appetite. This was also a transitional period when cruises were holding onto the vestiges and traditions of luxury ocean liners. All cruise lines had strict dress codes, requiring formal attire some evenings (people brought tuxedos!). The crew were largely Southern and Eastern European. As a kid who had never traveled outside North America, it felt like I was LARPing as James Bond.

When I moved out of my parents’ house for college, I wanted a change of scenery. While I had the option to move to a “college town”, I instead chose to live in a large city. And I loved it. It was like living on a cruise, all year round: Activities galore, amazing food, and all within a short distance of each other. A friend could call me up and say, ”Hey, we are hanging out at [X], would you like to join us?” And, regardless of where X was in the city, I could meet them there within fifteen minutes either by walking, biking, or taking public transport.

I didn’t need cruises anymore.

Preface

This year, for his birthday, my father only had one request: that he and his extended family take a cruise to celebrate. I just returned from that cruise, and it was a very different experience from the ones of my youth.

As an adult who had by this point lived the majority of his life in large cities, all I wanted to do was lay by a pool or, preferably, the beach all day and read a book. Those are both difficult things when you’re sharing a crowded pool space with over six thousand other people, and the ship doesn’t typically dock close to a good beach. Skating rink? Gimmicky specialty restaurants? Luxury shopping spree? Laser tag? Pub trivia? Theater productions? Comedy shows? I can do all of those things any day of the week a short distance from my house. When I vacation, I want to escape all that freneticism.

My wife, kids, and I were the only urbanites in our group, and my parents didn’t seem to comprehend why we had such little interest in all the activities. And then it dawned on me: A cruise is just a simulated city. Why would I want an artificial version of what I already have?

So, lying down on a deck chair, instead of reading my book, I started writing. The idea of simulated urbanism isn’t new, but it’s typically discussed in terms of curated amusement parks like Disney and the emergence of suburban “lifestyle center” developments. Therefore, initially, my goal was to channel this insight into as obnoxious a treatise as possible, in order to trigger my suburbanite traveling companions. Simulated urbanism? That reminded me of Baudrillard! I would make it a completely over-the-top academic analysis of the topic.

The following was compiled from a series of texts I sent to our group chat throughout the cruise.

Abstract

This article explores the paradox of vacation preferences among suburban Americans who gravitate toward densely populated environments such as cruises, European cities, and amusement parks, despite residing in sparsely populated areas. It examines how cruises and lifestyle centers, which mimic urban density while offering suburban convenience, satisfy the suburban desire for urban-like experiences. The article contrasts these preferences with those of urban Americans, who experience density daily and may seek different vacation experiences. By analyzing the dynamics of suburban and urban vacation choices, we highlight the complex interplay between suburban living and the pursuit of urban escapism.

Simulated Urbanism

Simulacra and Simulation

Metamodernism

Suburbanites’ predilections for cruising can be interpreted through the theoretical framework of metamodernism, which posits an oscillation between opposing cultural and experiential paradigms. The cruise experience encapsulates a synthesis of modernist aspirations for progress, order, and structured entertainment, alongside a postmodern sensibility characterized by irony and skepticism towards mass consumerism and the spectacle. This dialectical tension aligns with metamodernism’s core principle of navigating and reconciling contradictions. Within the confines of a cruise, suburbanites engage with the modernist ideal of escape and luxury, encountering a curated simulacrum that offers both adventure and novelty. Simultaneously, they remain cognizant of the inherent artifice and commodification intrinsic to the cruise experience, reflecting a postmodern consciousness of the limitations and constructed nature of such escapism.

Furthermore, the pragmatic idealism inherent in metamodernism is evident in the suburban pursuit of cruising, representing a quest for authenticity within a meticulously orchestrated environment. Suburbanites partake in cruising as a form of meaningful escapism that, although commodified, facilitates genuine opportunities for relaxation, social interaction, and cultural exploration. This dynamic reflects a metamodern synthesis of sincerity and irony, wherein participants seek genuine engagement and fulfillment while maintaining an awareness of the artificial and consumerist underpinnings of the cruise industry. The cruise, thus, serves as a microcosm of metamodern cultural hybridity, integrating diverse influences and experiences into a cohesive assemblage that enables suburbanites to navigate the complexities of contemporary existence with both optimism and reflexivity. This exemplifies the metamodern tension between the yearning for authentic connection and the recognition of its mediated nature, embodying a dialectical interplay that is central to metamodern thought.

Dialectics

(To be read as if dictated by Slavoj Žižek.)

From a Hegelian perspective, urbanites’ preferences for relaxing vacations can be understood through the lens of dialectical progression and the quest for synthesis between opposing elements in their lives. Hegel’s philosophy emphasizes the process of thesis, antithesis, and synthesis, [sniff] where the contradictions and tensions between different aspects of existence lead to the development of higher levels of understanding and being. A dance of contradictions and tensions.

Urbanites are like rats in a maze of their own making, living in this frenetic environment of constant stimulation and complexity. So, what do they do? They escape to a vacation that provides the antithesis of urban life, a necessary counterbalance that allows them to confront the contradictions of their daily existence.

In this dialectical process, the vacation can be seen as a moment of synthesis, where urbanites integrate the contrasting aspects of their existence—work and leisure, complexity and simplicity, stimulation and relaxation. Through this synthesis, they achieve a more harmonious state of being, temporarily resolving the contradictions inherent in their lives. [nose pull] Hegel might argue that this pursuit of balance is part of a broader process of self-realization and development, as individuals continually seek to reconcile opposing forces within themselves and their environments. This dialectical movement reflects a deeper philosophical journey toward self-awareness and fulfillment, where each vacation experience contributes to a more nuanced understanding of personal and existential needs.

Moreover, Hegel would likely emphasize that this process is not static but dynamic, as urbanites constantly redefine and re-evaluate their desires and experiences in pursuit of higher forms of understanding and contentment. [sniff] This ongoing dialectical interaction between urban life and vacation preferences underscores the complexity of human existence and the continuous evolution of individual consciousness within the broader historical and cultural context.

What Would Marx Say?

(For extra fun, to be read as if dictated by Jordan Peterson.)

When we examine the suburbanite’s preference for urban-like vacation experiences—such as cruising or visiting bustling cities—through the lens of Marxist theory, we uncover something quite profound about the alienation inherent in capitalist societies. Suburban life is often marked by routine and compartmentalization, a strong reliance on cars, and an emphasis on private space. This creates an environment of isolation and fragmentation, which Marx identified as symptomatic of capitalist production. The sprawling nature of suburbia physically separates individuals from their workplaces, social hubs, and cultural activities, generating a dichotomy between home life and community engagement. This alienation from collective social experiences mirrors the detachment workers feel from the products of their labor and from each other in a capitalist framework.

Thus, when suburbanites seek out vacations in dense, walkable environments, they’re searching for a temporary reprieve from this isolation. These vacations allow them to engage with the social interactions and cultural experiences that are often missing from their everyday lives. In this way, vacations become a commodified form of leisure within capitalist society, packaged and sold as products designed to alleviate the stresses of alienation and labor. Suburbanites, who feel the pressures of maintaining a lifestyle dictated by capitalist norms—like homeownership and consumerism—turn to vacations as a form of respite from these demands. Cruises and urban vacations offer a concentrated form of entertainment and cultural engagement, providing an illusion of freedom and choice that contrasts with the regulated and constrained nature of suburban life. While these vacations temporarily satisfy the need for genuine human connection and cultural enrichment, Marxist theory would argue that they also reinforce the capitalist cycle, as individuals must return to their suburban routines to earn the means to participate in such leisure activities. Thus, vacations, though they offer a brief escape from alienation, ultimately underscore the pervasive influence of capitalism on leisure and personal fulfillment.

Conclusions

As I reflect on the whirlwind of contradictions, philosophies, and cultural dynamics explored in this article, I must admit that I find myself utterly exhausted. Much like the aftermath of a cruise, where the buffet line feels both endless and insurmountable, I am too fatigued to draw any tidy conclusions. So, dear reader, as I lean back in my metaphorical deck chair, I invite you to navigate these intellectual waters and draw your own conclusions. Like the towel animals on your cabin bed, reality might be folded and shaped in surprising ways, but the essence remains yours to unravel. Bon voyage in your own journey of trolling! Or is it trawling?

Last week, news about CVE-2023-21036, nicknamed the “aCropalypse,” spread across Twitter and other media, and my colleague Henrik Brodin quickly realized that the underlying flaw could be detected by our tool, PolyTracker. Coincidentally, Henrik Brodin, Marek Surovič, and I wrote a paper that describes this class of bugs, defines a novel approach for detecting them, and introduces our implementation and tooling. It will appear at this year’s workshop on Language-Theoretic Security (LangSec) at the IEEE Security and Privacy Symposium.

The remainder of this blog post describes the bug and how it could have been detected or even prevented using our tools.

This is an excerpt from the Trail of Bits blog. You can read the full post here.

A couple of years ago I released PolyFile: a utility to identify and map the semantic structure of files, including polyglots, chimeras, and schizophrenic files. It’s a bit like file, binwalk, and Kaitai Struct all rolled into one. PolyFile initially used the TRiD definition database for file identification. However, this database was both too slow and prone to misclassification, so we decided to switch to libmagic, the ubiquitous library behind the file command.

This is an excerpt from the Trail of Bits blog. You can read the full post here.

I am proud to announce the release of it-depends, an open-source tool for automatic enumeration of dependencies. You simply point it to a source code repository, and it will build a graph with the required dependencies. It-depends currently supports cargo, npm, pip, go, CMake, and autotools codebases, packages in their associated package managers, and Ubuntu apt.

This is an excerpt from the Trail of Bits blog. You can read the full post here.

I recently created a challenge for the justCTF competition titled PDF is broken, and so is this file. It demonstrates some of the PDF file format’s idiosyncrasies in a bit of an unusual steganographic puzzle. CTF challenges that amount to finding a steganographic needle in a haystack are rarely enlightening, let alone enjoyable. LiveOverflow recently had an excellent video on file format tricks and concludes with a similar sentiment. Therefore, I designed this challenge to teach justCTF participants some PDF tricks and how some of the open source tools I’ve helped develop can make easy work of these forensic challenges.

Read the full post on the Trail of Bits blog for spoilers on how to solve the puzzle.

This is an excerpt from the Trail of Bits blog. You can read the full post here.