This is a personal blog. My other stuff: book | home page | Twitter | CNC robotics | electronics

June 29, 2015

Poland vs the United States: suburban sprawl

[ This is the eighth entry in a short series of articles about Poland. To start from the beginning, click here. ]

If you live in any other western country, your perception of the United States is bound to be profoundly influenced by Hollywood. You may think you're immune to it, but you are not: sure, you can sneer at the ridiculous plot holes or the gratuitous patriotism in American blockbusters - but the establishing shots of high-rise cityscapes of Manhattan or Los Angeles will be seared into your mind. These images will color your expectations and your understanding of the country in more ways than you may expect.

Because of this phenomenon, urban dwellers from Europe who come to visit the US may be in for a surprise: the country will probably feel a lot more rural than they would have thought. They will get to marvel the grand cities and the iconic skyscrapers; but chances are, this scenery will quickly morph not into the familiar urban jungle of massive apartment blocks seen throughout much of Europe, but into the endless suburban sprawl of single-family homes and strip malls.

For most Americans, this vast, low-density suburban landscape is the backdrop of their everyday lives. Take San Francisco: just 800,000 people live in the city proper. The San Francisco Bay Area, the home to 8 million residents and the location of the largest and most influential tech hub in the world, is nothing more than an enormous stretch of greenery peppered with detached homes, unassuming two-story office buildings, and roadside car dealerships. Heck, even New York City, by far the largest urban conglomeration in America, is just a blip on the radar compared to the colossal suburban sprawl that engulfs the region - stretching all the way from Massachusetts to Washington D.C.

The raw numbers paint a similar picture: in Poland, the average population density is around 125 people per square kilometer; in the more densely populated Germany, the figure is closer to 220. In comparison, with fewer than 35 people per km2, the United States comes out looking like a barren wasteland. The country has many expanses of untouched wilderness - and quite a few rural regions where the residents get by without as little as a postal address, a nearby fire station, a police department, or a hospital.

Awareness of the predominantly suburban and rural character of much of the US is vital to understanding some the national stereotypes that may seem bizarre or archaic to urban-dwelling Europeans. It certainly helps explain the limited availability of public transportation, or the residents' love for rifles and gas-guzzling pickup trucks. The survivalist "prepper" culture, focused on self-sufficiency in the face of disaster, is another cultural phenomenon that although seemingly odd, is not just pure lunacy; in the past few decades, millions of Americans had to evacuate or dig in in response to hurricanes, wildfires, earthquakes, or floods.

The stark difference between urban and rural living can also make it easier to grasp some of the ideological clashes between the big-city liberal progressives and the traditionally conservative dwellers of the so-called "flyover states". Sometimes, the conservatives are simply on the wrong side of history; but on some other occasions, the city-raised politicians, scholars, and journalists are too eager to paint the whole nation with the same brush. Take something as trivial as car efficiency standards: they will rub you one way if you take subway to the office and drive your compact car to the grocery store; and another if you ever needed to haul firewood or construction materials on the back of your Ford F-150.

June 28, 2015

Poland vs the United States: friends & acquaintances

[ This is the seventh entry in a short series of articles about Poland. To start from the beginning, click here. ]

Cultural stereotypes are a dangerous and corrosive thing. They teach us that Poles are a tribe of thieving simpletons; or that Americans are arrogant, violent, and obese. And that's just the ethnicities that get off easy: the perception of blacks, Muslims, or European Jews can be far more vicious, often serving a pretext for violent hate crime.

At the same time, there is no denying that certain unique archetypes are etched into the fabric of every society. I'd also posit that when cultures come into contact with each other, there is an uncanny valley effect at play: the more similar the nations are, the easier it is for travelers to instinctively pick up the subtle variations - and to misread them as the personality quirks of the people they interact with.

For Poles who settle in the United States, the most striking contrast of this sort must be the persistence with which Americans want to engage in oddly personal small talk: you will be always greeted with "how are you?", be it by the cashier at a grocery store, by your mailman, by the park ranger met at a trail, or by the waiter serving your food at a restaurant. The social expectation is to share short pleasantries or announce a brief piece of good news. But if your answer is overly specific or focuses on a negative event, you may be given quizzical looks and the conversation will stall.

To many of my compatriots, the exchange - lacking any apparent purpose - feels uncomfortable and insincere. I try not to look at it in a cynical way: the upbeat chit-chat, repeated over and over again, can probably make your day a bit better and a tad more fun. This constrained form of communication also provides something to build on the next time you see that person, even if every individual interaction is necessarily non-committal and brief.

Another explanation for the forced positivity may have to do with the pervasive can-do spirit at the core of the American culture. The national ethos of self-determination and unconstrained social mobility flies in the face of the daily struggles of disadvantaged citizens - but it remains a fundamental part of the cultural identity of the United States. The American Dream manifests itself everywhere, from the country songs of the Midwest to the high-tech entrepreneurship of the Silicon Valley. Your friends, coworkers, neighbors, and even complete strangers are there to support you when a calamity strikes - but dwelling on everyday mishaps is almost universally seen as a weakness that one needs to overcome in order to succeed in life.

In this regard, the Polish culture is strikingly different. After hundreds of years of political repression and foreign control, Poles have developed a colorful tradition of sarcastic humor and idle lamentation. This coping mechanism functions to this day: to a Pole, being asked about your day is seen as an invitation to air all the petty grievances; you wouldn't expect a friend to smile, exclaim "I'm doing great!", and move on. Complaining about politics or work is how you build rapport with your peers. In fact, being overly upbeat or talking about professional success or accomplishment is likely to be met with suspicion or scorn. If you're a successful entrepreneur, you will probably open by complaining about your dealings with the Polish equivalent of the IRS.

In many ways, the Polish approach to chit-chat is more genuine and less rigid. At the same time, I feel that the negativity comes at a price; meeting a cranky clerk at a store sets the tone for the remainder of your day. The constant pessimism can also dampen some altruistic instincts: relatively few people in Poland get engaged in their communities or dedicate themselves to other forms of civic service. It is more accepted to just complain about the ways things are.

Interestingly, in the United States, the boundaries that govern the conversations with complete strangers also extend into the workplace. When interacting with casual acquaintances, sarcasm is seen as jarring, while petty grumbling is perceived as an off-putting and unproductive personality trait. Off-color humor, widely tolerated in Poland, is usually inappropriate in white collar environments; doubly so if it comes at the expense of women, immigrants, or other disadvantaged social groups.

Some Europeans characterize the workplace etiquette in the US as political correctness run amok. There are situations where political correctness can stifle free speech, but I don't think it's one of them; for most part, not hearing political rants or jokes about blondes or Jews just makes the world a bit better, even if the comments are uttered with no ill intent. Violating these rules will not necessarily get you in trouble, but in a culturally diverse society, it can make it harder to find new friends.

[ To proceed to the next article in the series, click here. ]

June 23, 2015

Poland vs the United States: civil liberties

[ This is the sixth entry in a short series of articles about Poland. To start from the beginning, click here. ]

I opened my comparison of Poland and the US with the topic of firearm ownership. I decided to take this route in part because of how alien the US gun culture may appear to outsiders - and because of how polarizing and interesting the subject is. But in today's entry, I wanted to take a step back and have a look at the other, more traditional civil liberties that will be more familiar to folks on the other side of the pond.

Before we dive in, it is probably important to note that the national ethos of the United States is very expressly built on the tradition of individualism and free enterprise. Of course, many words can be written about the disconnection between this romanticized vision and complex realities of entrepreneurship or social mobility in the face of multi-generational poverty and failing inner-city schools (it may be a fitting subject for another post). But the perception still counts: in much of Europe, the government is seen less as a guarantor of civil liberties, and more as a provider of basic needs. The inverse is more true in the US; the armed forces and small businesses enjoy the two top spots in institutional trustworthiness surveys; federal legislators come dead last. This sentiment shapes many of the ongoing political debates - not just around individual freedoms, but also as related to public healthcare or the regulation of commerce. The virtues of self-sufficiency and laissez-faire capitalism seem far more self-evident to the citizens of the US than they are in the EU.

With that in mind, let's start with the freedom of speech. A cherished tradition in the western world, this liberty is nevertheless subordinate to a number of collectivist social engineering goals across the whole old continent; for example, strong prohibitions exist on the promotion of Nazi ideology or symbolism, or on the mere practice of denying the Holocaust. The freedom of speech is also trumped by the right to privacy, including the hotly-debated right to be forgotten on the Internet. Other, more exotic restrictions implemented in several places in Europe include the prohibition against insulting any acting heads of state; in Poland, people have been prosecuted for hurling childish insults at the Pope or at the outgoing Polish president. Of course, the enforcement is patently selective: in today's political climate, no one will be charged for calling Mr. Putin a thug.

The US takes a more absolutist view of the First Amendment, with many hate groups enjoying far-reaching impunity enshrined in the judicial standards put forward not by politicians, but by the unusually powerful US Supreme Court. The notion of "speech" is also interpreted very broadly, extending to many forms of artistic, religious, and political expression; in particular, the European niqab and burka bans would be patently illegal in the United States and aren't even the subject of serious debate. The concept of homeschooling, banned or heavily regulated in some parts of Europe, is seen by some through the same constitutional prism. Last but not least, there is the controversial Citizens United decision, holding that some forms of financial support provided to political causes can be equated with constitutionally protected speech; again, the ruling came not from the easily influenced politicians, but from the Supreme Court.

As an aside, despite the use of freedom-of-speech restrictions as a tool for rooting out anti-Semitism and hate speech in Europe, the contemporary US may be providing a less fertile ground for racism and xenophobia than at least some parts of the EU. The country still struggles with its dark past and the murky reality of racial discrimination - but despite the stereotypes, the incidence of at least some types of casual racism in today's America seems lower than in much of Europe. The pattern is also evident in political discourse; many of the openly xenophobic opinions or legislative proposals put forward by European populist politicians would face broad condemnation in the US. Some authors argue that the old continent is facing a profound new wave of Islamophobia and hatred toward Jews; in countries such as Greece and Hungary, more than 60% of population seems to be holding such views. In Poland, more than 40% say that Jews hold too much influence in business - a surreal claim, given that that there are just several thousand Jews living in the country of 38 million. My own memories from growing up in that country are that of schoolkids almost universally using "you Jew!" as a mortal insult. The defacement of Jewish graves and monuments, or anti-Semitic graffiti, posters, and sports chants are far more common than they should be. It's difficult to understand if restrictions on free speech suppress the sentiments or make them worse, but at the very least, the success of the policies is not clear-cut.

Other civil liberties uniquely revered in the United States put limits on the ability of the government to intrude into private lives through unwarranted searches and seizures. The stereotypical view of the US is that of a dystopian surveillance state, epitomized by the recent focus on warrantless surveillance or secret FISA courts. But having worked for a telecommunications company in Poland, my own sentiment is that law enforcement and intelligence agencies in Europe tend to operate with far more impunity and far less legal oversight; the intelligence community in particular is often engaged in politically motivated domestic investigations that should raise an eyebrow or two. In most of these countries, citizens are not afforded powerful tools such as FOIA requests, do not benefit from a tradition of protected investigative journalism and whistleblowing, and can't work with influential organizations such as the American Civil Liberties Union; there is also no history of scandals nearly as dramatic and transformative as Watergate. In the States, I feel that all that helped to create an imperfect but valuable balance between the needs of the government and the rights of the people - and instill higher ethical standards in the law enforcement and intelligence community. The individualist spirit helps, too: quite a few states and municipalities go as far as banning traffic enforcement cameras because of how they rob suspects of the ability to face the accuser in court.

On some other fronts, the United States needs to face justified criticism. The harsh and overcrowded penal system treats some offenders unfairly; it is a product of populist sentiments influenced by the crime waves of the twentieth century and fueled by the dysfunctional War on Drugs; while Polish prisons may not be much better, some of the ideas implemented elsewhere in Europe seem to make a clear difference. They are difficult to adopt in the States chiefly because they do not fit the folksy "tough on crime" image that many American politicians take pride in.

In the same vein, police brutality, disparagingly faced by the poor and the minorities, is another black mark for individual rights. The death penalty, albeit infrequent and reserved for most heinous crimes, stands on increasingly shaky moral grounds - even if it faces steady public support. The indefinite detention and torture of terrorism suspects, with the knowledge and complicity of many other European states, deserves nothing but scorn. Civil forfeiture is a bizarre concept that seems to violate the spirit of the Fourth Amendment by applying unreasonably relaxed standards for certain types of seizures - although in all likelihood, its days are coming to an end.

As usual, the picture is complex and it's hard to declare the superiority of any single approach to individual liberties. Europe and the United States have much in common, but also differ in very interesting ways.

[ To proceed to the next article in the series, click here. ]

June 22, 2015

A bit more on firearms in the US

Perhaps not surprisingly, my previous blog post sparked several interesting discussions with my Polish friends who took a more decisive view of the social costs of firearm ownership, or who saw the Second Amendment as a barbaric construct with no place in today's world. Their opinions reminded me of my own attitude some ten years ago; in this brief follow-up, I wanted to share several data points that convinced me to take a more measured stance.

Let's start with the basics: most estimates place the number of guns in the United States at 300 million - that's roughly one firearm per every single resident. In Gallup polls, roughly 40-50% of all households report having a gun, frequently more than one. The demographics of firearm ownership are more uniform than stereotypes may imply; there is some variance across regions, political affiliations, and genders - but it tends to fall within fairly narrow bands.

An overwhelming majority of gun owners cite personal safety as the leading motive for purchasing a firearm; hunting and recreation activities come strong second. The defensive aspect of firearm ownership is of special note, because it can potentially provide an argument for protecting the right to bear arms even when it comes at an elevated cost to the society as a whole.

The self-defense argument is sometimes dismissed as pure fantasy - and it's only fair to ask for evidence that goes beyond the anecdotes about Katrina or other catastrophic events. There is no precise data about the frequency with which firearms are routinely used to deter threats; the results of scientific polls are open to interpretation and vary significantly depending on sampling methods and questions asked. That said, a recent meta-analysis from Centers for Disease Control and Prevention provided some general bounds:

"Defensive use of guns by crime victims is a common occurrence, although the exact number remains disputed (Cook and Ludwig, 1996; Kleck, 2001a). Almost all national survey estimates indicate that defensive gun uses by victims are at least as common as offensive uses by criminals, with estimates of annual uses ranging from about 500,000 to more than 3 million."

The study also goes on to say:

"A different issue is whether defensive uses of guns, however numerous or rare they may be, are effective in preventing injury to the gun-wielding crime victim. Studies that directly assessed the effect of actual defensive uses of guns (i.e., incidents in which a gun was “used” by the crime victim in the sense of attacking or threatening an offender) have found consistently lower injury rates among gun-using crime victims compared with victims who used other self-protective strategies."

An argument can be made that the availability of firearms translates to higher rates of violent crime, thus elevating the likelihood of encounters where a defensive firearm would be useful. That said, such an effect does not seem to be particularly evident. For example, the United States comes out favorably in statistics related to assault, rape, and robbery - that is, compared to other OECD countries with far lower firearm ownership rates.

The area where the United States clearly falls behind other developed countries are homicides; the per-capita figures are almost three times as high as in much of the European Union. And indeed, the bulk of intentional homicides - some 11 thousand deaths a year - trace back to firearms.

That said, the origins of this tragic situation may be more elusive than they at first appear. For one, non-gun-related homicides happen in the US at a higher rate than in many other countries, too. In addition, no clear pattern emerges when comparing homicide rates across states with permissive and restrictive gun ownership laws. Some of the lowest per-capita homicide figures can be found in extremely gun-friendly states such as Idaho, Utah, or Vermont; whereas highly-regulated Washington D.C., Maryland, Illinois, and California all rank pretty high. It is likely that factors such as population density, urban poverty, and drug-related gang activities play a far more significant role, compared to the ease with which law-abiding citizens may purchase or bear arms. One CDC study on the topic concluded with:

"The Task Force found insufficient evidence to determine the effectiveness of any of the firearms laws or combinations of laws reviewed on violent outcomes."

This does not imply that legislative approaches are necessarily ineffective; for example, it seems pretty reasonable to assume that background checks or waiting periods do save lives. Similarly, safe storage requirements would likely prevent dozens of child deaths, although they would probably make firearms less useful for self-defense. But for the hundreds of sometimes far-fetched gun control proposals introduced every year on federal and state level, emotions often take place of real data, poisoning the debate around gun laws and ultimately bringing little or no public benefit. Some of the recent oddball legislation includes attempts to mandate costly liability insurance or ammunition purchase permits, and to ban ammo sales over the Internet.

Meanwhile, with sharp declines in crime continuing for the past 20 years, the public opinion is increasingly in favor of broad, reasonably policed gun ownership; for example, more than 70% respondents to one Gallup poll are against the restrictive handgun bans of the sort attempted in Chicago, San Francisco, or Washington D.C.; and in a recent Rasmussen poll, only 22% say that they would feel safer in a neighborhood where people are not allowed to keep guns. Even the National Rifle Association - a staunchly conservative organization vilified by gun control advocates and liberal pundits - enjoys a pretty reasonable approval rating across many demographics: 54% overall and 71% in households with a gun. And unlike most other large-scale lobbying groups, it is funded largely through individual memberships, small-scale donations, and purchase round-ups.

America's attitude to guns is a choice, not a necessity. It is also true that gun violence is a devastating problem; its emotional horror and lasting social impact can't be possibly captured in any cold, dry statistic alone. But there is also nuance and reason to the gun control debate that is sometimes hard for newcomers from more firearm-averse parts of the world to see.

[ To proceed to the next article in the series, click here. ]

June 14, 2015

Poland vs the United States: firearms

[ This is the fourth entry in a short series of articles about Poland. To start from the beginning, click here. ]

I spent roughly half of my adult life in Poland; for the other half, we lived in the United States. Because of this, my Polish friends sometimes ask about the cultural differences between the two countries. I always struggle to answer on the spot, so I decided to explore some of the most striking dissimilarities in a series of short blog posts. It's only fitting to start with guns.

Poland has long had one of the strictest firearms laws in the world, far ahead of most other countries in Europe. The roots of this policy are difficult to pinpoint, but it may have had to do with the years of foreign partitions, followed by the Soviet-imposed communist rule; in those trying times, private militias must have been seen as a grave threat to the social order and to the personal safety of the ruling class. Whatever the original causes, the effect is that in today's Poland, there is almost no tradition of gun ownership or hobby shooting sports; the country averages just around one firearm per 100 residents, compared to almost seven in the UK or thirty in Germany. It's likely that most Poles do not even know anyone who legally owns a gun.

In many ways, the United States may seem like the polar opposite; we have enough privately-owned firearms to equip almost every single man, woman, and child. In much of the country, there is no permitting process for new purchases and no registration requirements for handguns, rifles, or shotguns. The weapons can be bought at trade shows, given to family members, or loaned to friends. If you want to own an AR-15, you can have it - no questions asked.

The right to bear arms is an ancient tradition going all the way back to the early days of the Republic, envisioned as a constitutional safeguard to resist feudal subjugation and to guarantee the sovereignty of the fledgling country. In the minds of some, the Second Amendment is still the only thing that stands between freedom and ruin; but for many others, gun ownership is simply an empowering family hobby pursued at any of the tens of thousands of shooting ranges all across the United States. In a country populated far less densely than Europe, there is also some undeniable utilitarian aspect to it all: for rural populations, rifles are seen as a necessity for defending properties against wild animals or scaring away criminals or drunken thugs.

And then, there is the dark side: the US leads the developed world in gun suicides and homicides. The causes of this phenomenon are complex and deeply intertwined with the American psyche; but it is dishonest to claim that easy access to firearms does not play a substantial role. Some of the most vivid pictures seared into people's minds are the infrequent but devastating school shootings. A more everyday occurrence are the police encounters that end tragically because of the presumption that any suspect - even a child - may be armed to the teeth.

Over the last century, the looming specter of gun violence has led to increasing federal and state regulation of firearms. It is probable that many of these rules save lives with little harm to civil liberties; examples may include restrictions on assault weapons or the requirement for background checks. But other policies try to reshape the society in more profound ways; for example, Chicago Washington D.C., and San Francisco imposed blanket bans on handgun ownership, while the officials in New Orleans attempted to forcibly disarm citizens in the wake of Katrina - presumably to curb vigilante justice in the ravaged city.

Such zealous legislation is inevitably struck down by courts, who in recent years tended to see the Second Amendment in no uncertain terms. Perversely, it also tends to backfire for gun control advocates: it contributes to a toxic atmosphere where many firearms enthusiasts and interest groups feel that their freedoms are under constant assault, and that to keep them, they need to fight each and every new proposal tooth and nail. For example, one of the sticking points for the National Rifle Association is that federal gun registries would make it easy for the "baddies" to confiscate all firearms in the country; that sounded like pure lunacy, but to many, it rings a lot less hollow after the New Orleans incident.

In Europe, and in Poland in particular, gun laws in the US are often seen as a deranged product of a powerful gun lobby that works against the will and to the detriment of normal citizens; some progressive politicians and scholars in the US adopt the same view. I came to this country firmly sharing that opinion; in my younger years, I remember being entranced by "Bowling for Columbine". Today, I see the reality as far more nuanced. Despite never having fired a gun in my life, if forced to take sides in this emotional clash between collectivism and civil rights, I'm less sure that collectivism would always get my vote.

[ Continued here... ]

June 11, 2015

New in AFL: persistent mode

Although American Fuzzy Lop comes with a couple of nifty performance optimizations, it still relies on a fairly resource-intensive routine that is common to most general-purpose fuzzers: it continually creates new processes, feeds them a single test case, and then discards them to start over from scratch.

To avoid the overhead of the notoriously slow execve() syscall and the linking process, the fuzzer automatically leverages the forkserver optimization, where new processes are cloned from a copy-on-write master perpetually kept in a virgin state. This allows many targets to be fuzzed faster than with other, conventional tools. But even with this hack, each new input still incurs the cost of fork(). On all supported OSes with the exception of MacOS X, the fork() call is actually surprisingly fast - but certainly does not come free.

For some common fuzzing targets, such as zlib or libpng, the constant cycle of forking and initialization is a significant and avoidable bottleneck. In many cases, the underlying APIs are either stateless, or can be reliably reset to a nearly-pristine state across inputs - so at least in principle, you don't have to throw away the child process after every single run. That's where in-process fuzzing tends to shine: in this scheme, the test cases are generated inline and fed to the underlying API in a custom-written, single-process loop. The speed gains offered by in-process fuzzing can be as high as 10x, but the approach comes at a price; for example, it is easily derailed by accidental memory leaks or DoS conditions in the tested code.

Well, the good news is that starting with version 1.81b, afl-fuzz supports an optional "persistent" mode that combines the benefits of in-process fuzzing with the robustness of a more traditional multi-process tool. In this scheme, the fuzzer feeds test cases to a separate, long-lived process that reads the input data, passes it to the instrumented API, notifies the parent about successful run by stopping its own execution; eventually, when resumed by the parent, the process simply loops back to the start. You need to write a minimalist harness to implement the loop, but AFL takes care of most of the remaining tricky stuff, including crash handling, stall detection, and the usual instrumentation magic that AFL is designed for:

int main(int argc, char** argv) {


  /* Reset state. */
  memset(buf, 0, 100);

  /* Read input data. */
  read(0, buf, 100);

  /* Parse it in some vulnerable way. You'd normally call a library here. */
  if (buf[0] != 'p') puts("error 1"); else
  if (buf[1] != 'w') puts("error 2"); else
  if (buf[2] != 'n') puts("error 3"); else

  /* Tell the parent that we're done. When resumed, loop back. */
  goto try_again;


For a more complete example, see experimental/persistent_demo/ and be sure to read the last section of llvm_mode/README.llvm. This feature is inspired by the work done by Kostya Serebryany on LibFuzzer (which is, in turn, inspired by AFL); additional credit goes to Christian Holler, who started a conversation that finally prompted me to integrate this mode with the tool.

May 20, 2015

Lesser-known features of afl-fuzz

AFL is designed to be simple to use, but there are quite a few advanced, time-saving features that may be easy to overlook. So, here are several useful tricks that aren't covered in README:

  • Test case postprocessing: need to fix up checksums or length fields in a particular file format? AFL supports modular postprocessors that can take care of this for you. See experimental/post_library/ for sample code and other tips.

  • Deferred forkserver: stuck with a binary that initializes a lot of stuff before actually getting to the input data? When using clang, you can avoid this CPU overhead by instructing AFL to clone the process from an already-initialized image. It's simpler than it sounds - have a look at llvm_mode/README.llvm for advice.

  • Helpful stats: in addition to using afl-plot to generate pretty progress graphs, you can also directly parse <out_dir>/fuzzer_stats for machine-readable statistics on any background tasks. The afl-whatsup script is a simple demo of that.

  • Faster resume: if you don't care about detecting non-deterministic behavior in tested binaries, set AFL_NO_VAR_CHECK=1 before resuming afl-fuzz jobs. It can speed things up by a factor of ten. While you're at it, be sure to see docs/perf_tips.txt for other performance tips.

  • Heterogeneous parallelization: the parallelization mechanism described in docs/parallel_fuzzing.txt can be very easily used to co-fuzz several different parsers using a shared corpus, or to seamlessly couple afl-fuzz to any other guided tools - say, symbolic execution frameworks.

  • Third-party tools: have a look at docs/sister_projects.txt for a collection of third-party tools that help you manage multiple instances of AFL, simplify crash triage, allow you to fuzz network servers or clients, and add support for languages such as Python or Go.

  • Minimizing stuff: when you have a crashing test case, afl-tmin will work even with non-instrumented binaries - so you can use it to shrink and simplify almost anything, even if it has nothing to do with AFL.


May 17, 2015

Oh, the places you won't go: Polonia in the United States

[ This is the third entry in a short series of articles about Poland. To start from the beginning, click here. ]

Naming the largest diasporas in the United States may seem like an easy task. For one, we have the deeply-assimilated families of German, Irish, Italian, and British immigrants. There is also a large Mexican community, unique for having a much higher percentage of members who were foreign-born.

Most people would venture a guess that India or China should come next; some may also suggest France, Denmark, or the Netherlands. They would be all wrong: the next spot on the list belongs to the massive Polish diaspora, estimated to be almost ten million strong.

Given its sheer size, the cultural influences of the Polish-American community are uncharacteristically subdued. There are precious few Poland-originating holiday traditions or ethnic foods. Outside a couple rapidly shrinking enclaves such as Avondale in Chicago or Greenpoint in New York City, you are unlikely to bump into posh Polish diners, pricey grocery stores, or flamboyant street parades. Children born to Polish immigrants in the US are seldom taught to read or write in their parents' language - and will probably know very little about their familial lineage or common ancestry.

Perhaps there just aren't that many bits of Polish culture to build on against the backdrop of Germanic, British, Italian, and Dutch influences that shaped the American life. Much like its German counterpart, the traditional Polish cuisine is obsessed chiefly with potatoes and meat. Today, we take pride in our pączki, but when pressed, we will sooner or later confess that they are just doughnuts by some other name. We can offer you some pierogi, but they will truly impress you only if you never had any ravioli or tortellini. We can also hook you up with some sausage, sauerkraut, pickles, ribs, or beer. On your way out, take a bite of our cheesecake or apple pie.

The holiday traditions run into the same challenge, perhaps with the exception of the infamous but niche Dyngus Day. The most commonly observed practice is that in line with much of Central Europe, Polish children may get their gifts in the evening on Christmas Eve, not in the morning on Christmas Day. Our traditional clothing looks distinctive, but it is ornate and archaic, making it compare unfavorably with the beautiful simplicity of wearing green on St. Patrick's Day, or getting hammered in suspenders come Oktoberfest.

Humor aside, a more powerful clue to the invisibility of the Polish diaspora may lie in its very history. In the twentieth century, the immigrants from Poland ended up occupying three isolated social strata, with relatively few opportunities for working together and developing any form of a shared cultural identity.

The first and most populous stratum of contemporary immigration were the common folk, displaced by the horrors of the war and the crippling poverty that followed under communist rule. Many of them worked menial jobs, spoke little or no English, and clustered around many of the traditionally Polish enclaves that offered them a degree of familiarity and support. For many years, they and their children faced blatant discrimination, epitomized by the popular "Polish jokes" in the 1960s and 1970s. The demeaning stereotypes that followed them everywhere prompted many Poles to adopt Americanized names, intermarry, and keep their origins a private affair.

The second stratum were the dissidents and the disillusioned intellectuals leaving Poland to escape the dysfunctional regime. Usually better-educated and more confident, they helped build the first proper Polish-American institutions, including local newspapers, community organizations, churches, shipping and travel companies, or banks. The members of this group felt much stronger national identity and perceived themselves as the guarantors of Polish interests abroad. With the fall of communism in Europe, many of them were incredulous that the former dignitaries were allowed to walk free and play a role in business and politics - a sentiment that still shapes their political views.

The big change in immigration trends came with the accession of Poland to the European Union. The unhappy and the disenfranchised would now overwhelmingly favor moving to Germany or to the UK, where they could take up residence without having to deal with restrictive immigration laws. The remaining US-bound migration shifted toward skilled, university-trained engineers and IT workers, many of whom gravitated toward tech hubs such as SF Bay Area, Seattle, or NYC. Having been born in the 1970s and 1980s, most of them remembered Poland as a thriving capitalist democracy; they were driven not by despair, but by the prospects of better pay or more interesting work.

All this nuance is easily lost on the people back home. Many of the left-wing and centrist pundits in Poland demonize the expats in hopes of mobilizing the more moderate domestic electorate. They paint a picture of a frighteningly powerful voting block that will prop up any fringe, conservative candidate, as long as they promise to rid Polish politics of the Soviet sleeper agents and other increasingly fictitious communist legacy.

Of course, for most part, such reputation is bunk; although a good percentage of Polish-Americans are very distrustful of left-leaning politicians in their country of origin, only a tiny percentage of them ever turns up to actually cast a ballot, and their overall influence on the results of Polish elections is slim. Contrary to how they are perceived, they also do not blindly cling on to social conservatism; in American elections, they usually vote for Democrats.

That said, repeated over and over again, the catchy narrative about dimwitted compatriots can take a life of its own. Several weeks ago, Longin Pastusiak, an eminent Polish publicist and polician, penned a piece characterizing Polish-Americans as simpletons who only have a very shallow appreciation for the Polish heritage and who meekly submit to the supposedly powerful influences of the Roman Catholic church. He is not alone in his views; many go even further and call for the diaspora's voting rights to be taken away.

Having overcome discrimination in the States only to face bureaucratic hurdles and prejudiced, vitriolic nonsense back home, it's no wonder that most of the Polish immigrants just want to blend in and move on. In the long haul, it's probably a big loss.

Crowds at Polish Days in San Francisco (2010)

[ For the next article in the series, click here. ]

May 13, 2015

Oh, the places you won't go: The politics of Poland

[ This is the second entry in a short series of articles about Poland. You probably want to read this one first. ]

Growing up in Poland in the 90s, I never cared much for politics. Back then, you wouldn't want to get overly attached to any political movement anyway: when a country of 38 million emerges from half a century of communist rule, you know there will be some kinks to iron out.

Sitting on the sidelines, I saw the views of others solidified by what seemed like happenstance. My mother, a promising white-collar worker cast aside by the new reality, leaned sharply to the left; she would sometimes wax lyrical about the good old days of socialism. My wife's father, a one-time Party member turned opposition activist, found himself playing a role for the increasingly polarizing right. My aunt, a mild-mannered professor of ethics, rose to prominence in the liberal Warsaw elites - and became one of the most outspoken voices of feminism and anticlericalism in the country. She had an uneasy but fruitful relationship with the centrist movement.

At the turn of the twentieth century, no matter which side you took, keeping up with the political landscape must have been a full-time job. The bitterly divided communist-era dissident circles splintered into dozens of ephemeral movements, with many familiar faces gravitating toward two camps: the economically liberal centrist party that flirted with the teachings of Margaret Thatcher; and the Christian nationalist movement that somewhat confusingly co-opted the notions of social solidarity with the underprivileged, but served that dish with a side dish of social conservatism and a vaguely suspicious attitude toward the EU.

On the other side of the political spectrum, many of the former Party dignitaries joined forces and reinvented themselves as modern-day, pro-European social democrats. Despite the branding, the post-communist camp adopted a set of conservative economic policies seldom distinguishable from the direction taken by the centrist bloc. They brandished secular, progressive social attitudes - but in a deeply-religious country where catechesis has a largely uncontested place in public schools, they never dared to experiment with them to any real extent.

In many ways, I found it easier to pinpoint what these political movements had in common, not what set them apart. Their old-school leaders, by and large raised and educated in the communist era, had little experience with good governance or true statesmanship. Looking back at it, I think that the dissident camp was driven to some extent by an innate sense of entitlement to the spoils of overthrowing the communist rule. Their years at the helm were punctuated by unsportsmanlike cronyism, by shady deals around the sale of state-owned enterprises, and by attempts to cling on to power by entering absurd and ultimately self-destructive alliances with populist agrarian or nationalist movements.

The former communists played a different card. They saw themselves as the qualified, level-headed alternative to the argumentative and erratic right. They nurtured an image of proven leaders, even if their experience amounted to running a dysfunctional Soviet satellite state into the ground and then skillfully changing their views. For many years, they fared well in elections, but eventually, the mainstream left ended with a bang: the boldest of the many political scandals in the 2000s - afera Rywina - exposed an attempt to extort $5M from a newspaper publisher in exchange for striking down an antitrust provision in the proposed Polish media law.

Many stable democracies can afford a period of government dysfunction. For a time, this was certainly true for Poland: every modern-day democratic government to date had enough common sense to keep pushing for the integration with NATO and the European Union, worked to strike down or at least superficially modernize many of the communist-era laws, and never refused a penny of foreign aid. The unstoppable influx of capital did the rest, ushering a period of unprecedented stability and growth. The cracks would show only when you interacted with the state bureaucracy: with many levels of government permeated by centrally-appointed and disinterested ruling-party loyalists, getting a pothole fixed or a stop sign installed could very well prove to be an insurmountable task.

In some ways, that period of insensitivity to bad governance may be coming to an end. Driven away by a decade of stagnant wages coupled with the rapidly growing costs of living, some 2-3 million mostly young Poles decided to leave the country and seek a better life in the UK, in Germany, and in other parts of the EU. This, combined with sub-replacement fertility rates, must have put tremendous strain on the already-inadequate social security system - a safety net where the net retirement benefits hover somewhere around $400 a month.

In the most recent presidential elections in Poland, the centrist incumbent, Bronisław Komorowski, was so sure of his victory that he shunned televised debate. The voters not only turned up in droves to give his conservative opponent a healthy lead, but some 20% of them opted for a fringe anti-establishment candidate - a former punk rock singer with a knack for catchy lyrics but no experience in politics. The future is unknowable, but in the runoff elections, the punk rock aficionados are unlikely to vote for status quo.

Many of the moral authorities in Poland share the same dissident roots with the current president and are sympathetic to Mr. Komorowski's plight. One professor of political sciences prayed for the "radicalized youth" to leave the country, apparently unaware of how radical and divisive his own words may sound. The incumbent president was quick to note that he always supported the few scattered policy proposals that can be attributed to the anti-establishment candidate. He went on to meet with the voters and rebuked a young person asking how to get by on $550 a month. The president's answer: get a loan or find a better job.

[ For the next article in the series, click here. ]

April 14, 2015

Finding bugs in SQLite, the easy way

SQLite is probably the most popular embedded database in use today; it is also known for being exceptionally well-tested and robust. In contrast to traditional SQL solutions, it does not rely on the usual network-based client-server architecture and does not employ a complex ACL model; this simplicity makes it comparatively safe.

At the same time, because of its versatility, SQLite sometimes finds use as the mechanism behind SQL-style query APIs that are exposed between privileged execution contexts and less-trusted code. For an example, look no further than the WebDB / WebSQL mechanism available in some browsers; in this setting, any vulnerabilities in the SQLite parser can open up the platform to attacks.

With this in mind, I decided to take SQLite for a spin with - you guessed it - afl-fuzz. As discussed some time ago, languages such as SQL tend to be difficult to stress-test in a fully automated manner: without an intricate model of the underlying grammar, random mutations are unlikely to generate anything but trivially broken statements. That said, afl-fuzz can usually leverage the injected instrumentation to sort out the grammar on its own. All I needed to get it started is a basic dictionary; for that, I took about 5 minutes to extract a list of reserved keywords from the SQLite docs (now included with the fuzzer as testcases/_extras/sql/). Next, I seeded the fuzzer with a single test case:

create table t1(one smallint);
insert into t1 values(1);
select * from t1;

This approach netted a decent number of interesting finds, some of which were mentioned in an earlier blog post that first introduced the dictionary feature. But when looking at the upstream fixes for the initial batch, I had a sudden moment of clarity and recalled that the developers of SQLite maintained a remarkably well-structured and comprehensive suite of hand-written test cases in their repository.

I figured that this body of working SQL statements may be a much better foundation for the fuzzer to build on, compared to my naive query - so I grepped the test cases out, split them into files, culled the resulting corpus with afl-cmin, and trimmed the inputs with afl-tmin. After a short while, I had around 550 files, averaging around 220 bytes each. I used them as a starting point for another run of afl-fuzz.

This configuration very quickly yielded a fair number of additional, unique fault conditions, ranging from NULL pointer dereferences, to memory fenceposts visible only under ASAN or Valgrind, to pretty straightforward uses of uninitialized pointers (link), bogus calls to free() (link), heap buffer overflows (link), and even stack-based ones (link). The resulting collection of 22 crashing test cases is included with the fuzzer in docs/vuln_samples/sqlite_*. They include some fairly ornate minimized inputs, say:

INSERT INTO t0(docid,x)VALUES(-1E0,'0(o');
SELECT docid FROM t0 WHERE t0 MATCH'"0*o"';

All in all, it's a pretty good return on investment for about 30 minutes of actual work - especially for a piece of software functionally tested and previously fuzzed to such a significant extent.

PS. I was truly impressed with Richard Hipp fixing each and every of these cases within a couple of hours of sending in a report. The fixes have been incorporated in version 3.8.9 of SQLite and have been public for a while, but there was no upstream advisory; depending on your use case, you may want to update soon.

March 30, 2015

On journeys

- 1 -

Poland is an ancient country whose history is deeply intertwined with that of the western civilization. In its glory days, the Polish-Lithuanian Commonwealth sprawled across vast expanses of land in central Europe, from Black Sea to Baltic Sea. But over the past two centuries, it suffered a series of military defeats and political partitions at the hands of its closest neighbors: Russia, Austria, Prussia, and - later - Germany.

After more than a hundred years of foreign rule, Poland re-emerged as an independent state in 1918, only to face the armies of Nazi Germany at the onset of World War II. With Poland's European allies reneging on their earlier military guarantees, the fierce fighting left the country in ruins. Some six million people have died within its borders - more than ten times the death toll in France or in the UK. Warsaw was reduced to a sea of rubble, with perhaps one in ten buildings still standing by the end of the war.

With the collapse of the Third Reich, the attendees of the Yalta Conference decided the new order of the post-war Europe. At Stalin's behest, Poland and its neighboring countries were placed under Soviet political and military control, forming what has become known as the Eastern Bloc.

Over the next several decades, the Soviet satellite states experienced widespread repression and economic decline. But weakened by the expense of the Cold War, the communist chokehold on the region eventually began to wane. In Poland, the introduction of martial law in 1981 could not put an end to sweeping labor unrest. Narrowly dodging the specter of Soviet intervention, the country regained its independence in 1989 and elected its first democratic government; many other Eastern Bloc countries soon followed suit.

Ever since then, Poland has enjoyed a period of unprecedented growth and has emerged as one of the more robust capitalist democracies in the region. In just two decades, it shed many of its backwardly, state-run heavy industries and adopted a modern, service-oriented economy. But the effects of the devastating war and the lost decades under communist rule still linger on - whether you look at the country's infrastructure, at its socrealist cityscapes, at its political traditions, or at the depressingly low median wage.

When thinking about the American involvement in the Cold War, people around the world may recall Vietnam, Bay of Pigs, or the proxy wars fought in the Middle East. But in Poland and many of its neighboring states, the picture you remember the most is the fall of the Berlin Wall.

- 2 -

I was born in Warsaw in the winter of 1981, at the onset of martial law, with armored vehicles rolling onto Polish streets. My mother, like many of her generation, moved to the capital in the sixties as a part of an effort to rebuild and repopulate the war-torn city. My grandma would tell eerie stories of Germans and Soviets marching through their home village somewhere in the west. I liked listening to the stories; almost every family in Poland had some to tell.

I did not get to know my father. I knew his name; he was a noted cinematographer who worked on big-ticket productions back in the day. He left my mother when I was very young and never showed interest in staying in touch. He had a wife and other children, so it might have been that.

Compared to him, mom hasn't done well for herself. We ended up in social housing in one of the worst parts of the city, on the right bank of the Vistula river. My early memories from school are that of classmates sniffing glue from crumpled grocery bags. I remember my family waiting in lines for rationed toilet paper and meat. As a kid, you don't think about it much.

The fall of communism came suddenly. I have a memory of grandma listening to broadcasts from Radio Free Europe, but I did not understand what they were all about. I remember my family cheering one afternoon, transfixed to a black-and-white TV screen. I recall my Russian language class morphing into English; I had my first taste of bananas and grapefruits. There is the image of the monument of Feliks Dzierżyński coming down. I remember being able to go to a better school on the other side of Warsaw - and getting mugged many times on the way.

The transformation brought great wealth to some, but many others have struggled to find their place in the fledgling and sometimes ruthless capitalist economy. Well-educated and well read, my mom ended up in the latter pack, at times barely making ends meet. I think she was in part a victim of circumstance, and in part a slave to way of thinking that did not permit the possibility of taking chances or pursuing happiness.

- 3 -

Mother always frowned upon popular culture, seeing it as unworthy of an educated mind. For a time, she insisted that I only listen to classical music. She angrily shunned video games, comic books, and cartoons. I think she perceived technology as trivia; the only field of science she held in high regard was abstract mathematics, perhaps for its detachment from the mundane world. She hoped that I would learn Latin, a language she could read and write; that I would practice drawing and painting; or that I would read more of the classics of modernist literature.

Of course, I did almost none of that. I hid my grunge rock tapes between Tchaikovsky, listened to the radio under the sheets, and watched the reruns of The A-Team while waiting for her to come back from work. I liked electronics and chemistry a lot more than math. And when I laid my hands on my first computer - an 8-bit relic of British engineering from 1982 - I soon knew that these machines, in their incredible complexity and flexibility, were what I wanted to spend my time on.

I suspected I could be a competent programmer, but never had enough faith in my skill. Yet, in learning about computers, I realized that I had a knack for understanding complex systems and poking holes in how they work. With a couple of friends, we joined the nascent information security community in Europe, comparing notes on mailing lists. Before long, we were taking on serious consulting projects for banks and the government - usually on weekends and after school, but sometimes skipping a class or two. Well, sometimes more than that.

All of the sudden, I was facing an odd choice. I could stop, stay in school and try to get a degree - going back every night to a cramped apartment, my mom sleeping on a folding bed in the kitchen, my personal space limited to a bare futon and a tiny desk. Or, I could seize the moment and try to make it on my own, without hoping that one day, my family would be able to give me a head start.

I moved out, dropped out of school, and took on a full-time job. It paid somewhere around $12,000 a year - a pittance anywhere west of the border, but a solid wage in Poland even today. Not much later, I was making two times as much, about the upper end of what one could hope for in this line of work. I promised myself to keep taking courses after hours, but I wasn't good at sticking to the plan. I moved in with my girlfriend, and at the age of 19, I felt for the first time that things were going to be all right.

- 4 -

Growing up in Europe, you get used to the barrage of low-brow swipes taken at the United States. Your local news will never pass up the opportunity to snicker about the advances of creationism somewhere in Kentucky. You can stay tuned for a panel of experts telling you about the vastly inferior schools, the medieval justice system, and the striking social inequality on the other side of the pond. But deep down inside, no matter how smug the critics are, or how seemingly convincing their arguments, the American culture still draws you in.

My moment of truth came in the summer of 2000. A company from Boston asked me if I'd like to talk about a position on their research team; I looked at the five-digit figure and could not believe my luck. Moving to the US was an unreasonable risk for a kid who could barely speak English and had no safety net to fall back to. But that did not matter: I knew I had no prospects of financial independence in Poland - and besides, I simply needed to experience the New World through my own eyes.

Of course, even with a job offer in hand, getting into the United States is not an easy task. An engineering degree and a willing employer opens up a straightforward path; it is simple enough that some companies would abuse the process to source cheap labor for menial, low-level jobs. With a visa tied to the petitioning company, such captive employees could not seek better wages or more rewarding work.

But without a degree, the options shrink drastically. For me, the only route would be a seldom-granted visa reserved for extraordinary skill - meant for the recipients of the Nobel Prize and other folks who truly stand out in their field of expertise. The attorneys looked over my publication record, citations, and the supporting letters from other well-known people in the field. Especially given my age, they thought we had a good shot. A few stressful months later, it turned out that they were right.

On the week of my twentieth birthday, I packed two suitcases and boarded a plane to Boston. My girlfriend joined me, miraculously securing a scholarship at a local university to continue her physics degree; her father helped her with some of the costs. We had no idea what we were doing; we had perhaps few hundred bucks on us, enough to get us through the first couple of days. Four thousand miles away from our place of birth, we were starting a brand new life.

- 5 -

The cultural shock gets you, but not in the sense you imagine. You expect big contrasts, a single eye-opening day to remember for the rest of your life. But driving down a highway in the middle of a New England winter, I couldn't believe how ordinary the world looked: just trees, boxy buildings, and pavements blanketed with dirty snow.

Instead of a moment of awe, you drown in a sea of small, inconsequential things, draining your energy and making you feel helpless and lost. It's how you turn on the shower; it's where you can find a grocery store; it's what they meant by that incessant "paper or plastic" question at the checkout line. It's how you get a mailbox key, how you make international calls, it's how you pay your bills with a check. It's the rules at the roundabout, it's your social security number, it's picking the right toll lane, it's getting your laundry done. It's setting up a dial-up account and finding the food you like in the sea of unfamiliar brands. It's doing all this without Google Maps or a Facebook group to connect with other expats nearby.

The other thing you don't expect is losing touch with your old friends; you can call or e-mail them every day, but your social frames of reference begin to drift apart, leaving less and less to talk about. The acquaintances you make in the office will probably never replace the folks you grew up with. We managed, but we weren't prepared for that.

- 6 -

In the summer, we had friends from Poland staying over for a couple of weeks. By the end of their trip, they asked to visit New York City one more time; we liked the Big Apple, so we took them on a familiar ride down I-90. One of them went to see the top of World Trade Center; the rest of us just walked around, grabbing something to eat before we all headed back. A few days later, we were all standing in front of a TV, watching September 11 unfold in real time.

We felt horror and outrage. But when we roamed the unsettlingly quiet streets of Boston, greeted by flags and cardboard signs urging American drivers to honk, we understood that we were strangers a long way from home - and that our future in this country hanged in the balance more than we would have thought.

Permanent residency is a status that gives a foreigner the right to live in the US and do almost anything they please - change jobs, start a business, or live off one's savings all the same. For many immigrants, the pursuit of this privilege can take a decade or more; for some others, it stays forever out of reach, forcing them to abandon the country in a matter of days as their visas expire or companies fold. With my O-1 visa, I always counted myself among the lucky ones. Sure, it tied me to an employer, but I figured that sorting it out wouldn't be a big deal.

That proved to be a mistake. In the wake of 9/11, an agency known as Immigration and Naturalization Services was being dismantled and replaced by a division within the Department of Homeland Security. My own seemingly straightforward immigration petition ended up somewhere in the bureaucratic vacuum that formed in between the two administrative bodies. I waited patiently, watching the deepening market slump, and seeing my employer's prospects get dimmer and dimmer every month. I was ready for the inevitable, with other offers in hand, prepared to make my move perhaps the very first moment I could. But the paperwork just would not come through. With the Boston office finally shutting down, we packed our bags and booked flights. We faced the painful admission that for three years, we chased nothing but a pipe dream. The only thing we had to show for it were two adopted cats, now sitting frightened somewhere in the cargo hold.

The now-worthless approval came through two months later; the lawyers, cheerful as ever, were happy to send me a scan. The hollowed-out remnants of my former employer were eventually bought by Symantec - the very place from where I had my backup offer in hand.

- 7 -

In a way, Europe's obsession with America's flaws made it easier to come home without ever explaining how the adventure really played out. When asked, I could just wing it: a mention of the death penalty or permissive gun laws would always get you a knowing nod, allowing the conversation to move on.

Playing to other people's preconceptions takes little effort; lying to yourself calls for more skill. It doesn't help that when you come back after three years away from home, you notice all the small things you simply used to tune out. The dilapidated road from the airport; the drab buildings on the other side of the river; the uneven pavements littered with dog poop; the dirty walls at my mother's place, with barely any space to turn. You can live with it, of course - but it's a reminder that you settled for less, and it's a sensation that follows you every step of the way.

But more than the sights, I couldn't forgive myself something else: that I was coming back home with just loose change in my pocket. There are some things that a failed communist state won't teach you, and personal finance is one of them; I always looked at money just as a reward for work, something you get to spend to brighten your day. The indulgences were never extravagant: perhaps I would take the cab more often, or have take-out every day. But no matter how much I made, I kept living paycheck-to-paycheck - the only way I knew, the way our family always did.

- 8 -

With a three-year stint in the US on your resume, you don't have a hard time finding a job in Poland. You face the music in a different way. I ended up with a salary around a fourth of what I used to make in Massachusetts, but I simply decided not to think about it much. I wanted to settle down, work on interesting projects, marry my girlfriend, have a child. I started doing consulting work whenever I could, setting almost all the proceeds aside.

After four years with T-Mobile in Poland, I had enough saved to get us through a year or so - and in a way, it changed the way I looked at my work. Being able to take on ambitious challenges and learn new things started to matter more than jumping ships for a modest salary bump. Burned by the folly of pursuing riches in a foreign land, I put a premium on boring professional growth.

Comically, all this introspection made me realize that from where I stood, I had almost nowhere left to go. Sure, Poland had telcos, refineries, banks - but they all consumed the technologies developed elsewhere, shipped here in a shrink-wrapped box; as far as their IT went, you could hardly tell the companies apart. To be a part of the cutting edge, you had to pack your bags, book a flight, and take a jump into the unknown. I sure as heck wasn't ready for that again.

And then, out of the blue, Google swooped in with an offer to work for them from the comfort of my home, dialing in for a videoconference every now and then. The starting pay was about the same, but I had no second thoughts. I didn't say it out loud, but deep down inside, I already knew what needed to happen next.

- 9 -

We moved back to the US in 2009, two years after taking the job, already on the hook for a good chunk of Google's product security and with the comfort of knowing where we stood. In a sense, my motive was petty: you could call it a desire to vindicate a failed adolescent dream. But in many other ways, I have grown fond of the country that shunned us once before; and I wanted our children to grow up without ever having to face the tough choices and the uncertain prospects I had to deal with in my earlier years.

This time, we knew exactly what to do: a quick stop at a grocery store on a way from the airport, followed by e-mail to our immigration folks to get the green card paperwork out the door. A bit more than half a decade later, we were standing in a theater in Campbell, reciting the Oath of Allegiance and clinging on to our new certificates of US citizenship.

The ceremony closed a long and interesting chapter in my life. But more importantly, standing in that hall with people from all over the globe made me realize that my story is not extraordinary; many of them had lived through experiences far more harrowing and captivating than mine. If anything, my tale is hard to tell apart from that of countless other immigrants from the former Eastern Bloc. By some estimates, in the US alone, the Polish diaspora is about 9 million strong.

I know that the Poland of today is not the Poland I grew up in. It's not not even the Poland I came back to in 2003; the gap to Western Europe is shrinking every single year. But I am grateful to now live in a country that welcomes more immigrants than any other place on Earth - and at the end of their journey, makes many of them them feel at home. It also makes me realize how small and misguided must be the conversations we are having about immigration - not just here, but all over the developed world.

[ For another article in s a short series about Poland, click here. ]

March 11, 2015

Another round of image bugs: PNG and JPEG XR

Today's release of MS15-024 and MS15-029 addresses two more image-related memory disclosure vulnerabilities in Internet Explorer - this time, affecting the little-known JPEG XR format supported by this browser, plus the far more familiar PNG. Similarly to the previously discussed bugs in MSIE TIFF and JPEG parsing, and to the BMP, ICO, and GIF and JPEG DHT & SOS flaws in Firefox and Chrome, these two were found with afl-fuzz. The earlier posts have more context - today, just enjoy some pretty pics, showing subsequent renderings of the same JPEG XR image:

Proof-of-concepts are here (JXR) and here (PNG). I am happy to report that Microsoft fixed them within roughly three months of the original report.

The total number of bugs squashed in this category is now ten. I have just one more multi-browser image parsing bug outstanding - but it should be an interesting one. Stay tuned.

February 10, 2015

Bi-level TIFFs and the tale of the unexpectedly early patch

Today's release of MS15-016 (CVE-2015-0061) fixes another of the series of browser memory disclosure bugs found with afl-fuzz - this time, related to the handling of bi-level (1-bpp) TIFFs in Internet Explorer (yup, MSIE displays TIFFs!). You can check out a simple proof-of-concept here, or simply enjoy this screenshot of eight subsequent renderings of the same TIFF file:

The vulnerability is conceptually similar to other previously-identified problems with GIF and JPEG handling in popular browsers (example 1, example 2), with the SOS handling bug in libjpeg, or the DHT bug in libjpeg-turbo (details here) - so I will try not to repeat the same points in this post.

Instead, I wanted to take note of what really sets this bug apart: Microsoft has addressed it in precisely 60 days, counting form my initial e-mail to the availability of a patch! This struck me as a big deal: although vulnerability research is not my full-time job, I do have a decent sample size - and I don't think I have seen this happen for any of the few dozen MSIE bugs that I reported to MSRC over the past few years. The average patch time always seemed to be closer to 6+ months - coupled with what the somewhat odd practice of withholding attribution in security bulletins and engaging in seemingly punitive PR outreach if the reporter ever went public before that.

I am very excited and hopeful that rapid patching is the new norm - and huge thanks to MSRC folks if so :-)

February 04, 2015

Symbolic execution in vuln research

There is no serious disagreement that symbolic execution has a remarkable potential for programatically detecting broad classes of security vulnerabilities in modern software. Fuzzing, in comparison, is an extremely crude tool: it's the banging-two-rocks-together way of doing business, as contrasted with brain surgery.

Because of this, it comes as no surprise that for the past decade or so, the topic of symbolic execution and related techniques has been the mainstay of almost every single self-respecting security conference around the globe. The tone of such presentations is often lofty: the slides and research papers are frequently accompanied by claims of extraordinary results and the proclamations of the imminent demise of less sophisticated tools.

Yet, despite the crippling and obvious limitations of fuzzing and the virtues of symbolic execution, there is one jarring discord: I'm fairly certain that probably around 70% of all remote code execution vulnerabilities disclosed in the past few years trace back to fairly "dumb" fuzzing tools, with the pattern showing little change over time. The remaining 30% is attributable almost exclusively to manual work - be it systematic code reviews, or just aimlessly poking the application in hopes of seeing it come apart. When you dig through public bug trackers, vendor advisories, and CVE assignments, the mark left by symbolic execution can be seen only with a magnifying glass.

This is an odd discrepancy, and one that is sometimes blamed on the practitioners being backwardly, stubborn, and ignorant. This may be true, but only to a very limited extent; ultimately, most geeks are quick to embrace the tools that serve them well. I think that the disconnect has its roots elsewhere:
  1. The code behind many of the most-cited, seminal publications on security-themed symbolic execution remains non-public; this is particularly true for Mayhem and SAGE. Implementation secrecy is fairly atypical in the security community, is usually viewed with distrust, and makes it difficult to independently evaluate, replicate, or build on top of the published results.

  2. The research often fails to fully acknowledge the limitations of the underlying methods - while seemingly being designed to work around these flaws. For example, the famed Mayhem experiment helped identify thousands of bugs, but most of them seemed to be remarkably trivial and affected only very obscure, seldom-used software packages with no significance to security. It is likely that the framework struggled with more practical issues in higher-value targets - a prospect that, especially if not addressed head-on, can lead to cynical responses and discourage further research.

  3. Any published comparisons to more established vulnerability-hunting techniques are almost always retrospective; for example, after the discovery of Heartbleed, several teams have claimed that their tools would have found the bug. But analyses that look at ways to reach an already-known fault condition are very susceptible to cognitive bias. Perhaps more importantly, it is always tempting to ask why the tools are not tasked with producing a steady stream of similarly high-impact, headline-grabbing bugs.
The uses of symbolic execution, concolic execution, static analysis, and other emerging technologies to spot substantial vulnerabilities in complex, unstructured, and non-annotated code are still in their infancy. The techniques suffer from many performance trade-offs and failure modes, and while there is no doubt that they will shape the future of infosec, thoughtful introspection will probably get us there sooner than bold claims with little or no follow-through. We need to move toward open-source frameworks, verifiable results, and solutions that work effortlessly and reliably for everyone, against almost any target. That's the domain where the traditional tools truly shine, and that's why they scale so well.

Ultimately, the key to winning the hearts and minds of practitioners is very simple: you need to show them how the proposed approach finds new, interesting bugs in the software they care about.

February 03, 2015

afl-fuzz: black-box binary fuzzing, perf improvements, and more

I had quite a few posts about afl-fuzz recently, mostly focusing on individual, newly-shipping features (say, the fork server, the crash explorer, or the grammar reconstruction logic). But this probably gets boring for people not interested in the tool, and doesn't necessarily add up to a coherent picture for those who do.

To trim down on AFL-themed posts, I decided to write down a technical summary of all the internals and maintain it as a part of the AFL home page. The document talks about quite a few different things, including:
  • The newly-added support for guided fuzzing of black-box, closed-source binaries (yes, it finally happened!),

  • Info about effector maps - a new feature that offers significant performance improvements for many types of fuzzing jobs,

  • Some hard data comparing the efficiency of evolutionary fuzzing and AFL-style instrumentation versus more traditional tools,

  • Discussion of many other details that have not been documented in depth until now - queue culling, file minimization, etc.
I'll try to show a bit more restraint with AFL-related news on this blog from now on, so if you want to stay in the loop on key developments, consider signing up for the afl-users@ mailing list.

January 27, 2015

Technical analysis of Qualys' GHOST

This morning, a leaked note from Qualys' external PR agency made us aware of GHOST. In this blog entry, our crack team of analysts examines the technical details of GHOST and makes a series of recommendations to better protect your enterprise from mishaps of this sort.

Figure 1: The logo of GHOST, courtesy of Qualys PR.

Internally, GHOST appears to be implemented as a lossy representation of a two-dimensional raster image, combining YCbCr chroma subsampling and DCT quantization techniques to achieve high compression rates; among security professionals, this technique is known as JPEG/JFIF. This compressed datastream maps to an underlying array of 8-bpp RGB pixels, arranged sequentially into a rectangular shape that is 300 pixels wide and 320 pixels high. The image is not accompanied by an embedded color profile; we must note that this poses a considerable risk that on some devices, the picture may not be rendered faithfully and that crucial information may be lost.

In addition to the compressed image data, the file also contains APP12, EXIF, and XMP sections totaling 818 bytes. This metadata tells us that the image has been created with Photoshop CC on Macintosh. Our security personnel notes that Photoshop CC is an obsolete version of the application, superseded last year by Photoshop CC 2014. In line with industry best practices and OWASP guidelines, we recommend all users to urgently upgrade their copy of Photoshop to avoid exposure to potential security risks.

The image file modification date returned by the HTTP server at is Thu, 02 Oct 2014 02:40:27 GMT (Last-Modified, link). The roughly 90-day delay between the creation of the image and the release of the advisory probably corresponds to the industry-standard period needed to test the materials with appropriate focus groups.

Removal of the metadata allows the JPEG image to be shrunk from 22,049 to 21,192 bytes (-4%) without any loss of image quality; enterprises wishing to conserve vulnerability-disclosure-related bandwidth may want to consider running jhead -purejpg to accomplish this goal.

Of course, all this mundane technical detail about JPEG images distracts us from the broader issue highlighted by the GHOST report. We're talking here about the fact that the JPEG compression is not particularly suitable for non-photographic content such as logos, especially when the graphics need to be reproduced with high fidelity or repeatedly incorporated into other work. To illustrate the ringing artifacts introduced by the lossy compression algorithm used by the JPEG file format, our investigative team prepared this enhanced visualization:

Figure 2: A critical flaw in GHOST: ringing artifacts.

Artifacts aside, our research has conclusively showed that the JPEG formats offers an inferior compression rate compared to some of the alternatives. In particular, when converted to a 12-color PNG and processed with pngcrush, the same image can be shrunk to 4,229 bytes (-80%):

Figure 3: Optimized GHOST after conversion to PNG.

PS. Tavis also points out that ">_" is not a standard unix shell prompt. We believe that such design errors can be automatically prevented with commercially-available static logo analysis tools.

PPS. On a more serious note, check out this message to get a sense of the risk your server may be at. Either way, it's smart to upgrade.

January 24, 2015

Looking back at three months of afl-fuzz

I originally released afl-fuzz, a security-oriented fuzzer driven by a simple genetic algorithm, somewhere in November of 2013. Back then, it was simply another take on an idea I first toyed with in 2007, inspired in large part by the work on fuzzer corpus distillation done by Tavis Ormandy. It almost ended up in the dustbin of history: early on, the project had many shortcomings, and I was swamped with other work - so I ended up not announcing it properly and not touching it for almost a year.

But then, when the "Shellshock" vulnerability came by in October 2014, and we were increasingly suspicious about the original patch, I decided to dust off an early incarnation of afl-fuzz and take it for a quick spin. I was actually pretty surprised at how good it turned out to be at navigating bash syntax - and how quickly it found additional bugs that weren't predicated simply on flipping random bits, but on being able to synthesize the syntax of the underlying files. A couple of additional tests confirmed that the underlying approach was probably worth more than I have given it credit for.

And so, over the past few months, afl-fuzz has seen almost constant development, with several releases every week. The changes range from sweeping performance and fuzzing strategy improvements, to a clever fork server design proposed by Jann Horn, to visualization capabilities sketched out by Michael Rash, to a crash exploration mode to help in impact analysis, to robust test case and corpus minimization tools (afl-tmin, afl-cmin), to spiffy grammar-aware modes that lessen the need for format-specific tools, to support for *BSD systems, MacOS X, Solaris... and much more.

Since then, afl-fuzz helped squash hundreds of bugs, in part due to a community of folks who found the tool to be fun to use. For example, it has been used by OpenBSD developers to beef up anything from pfctl, to tcpdump, to rcs. Jodie Cunningham relied on it to identify dozens of distinct issues in ImageMagick (GraphicsMagick team had kind words for the tool, too). LLVM developers run it on a corpus of C files to get rid of a sizable pile of compiler issues. Jakub Wilk has worked tirelessly to squash numerous vulnerabilities in the Debian tree. Alex Eubanks used it to find security bugs in PHP and libpng. Many other folks took on "hot" projects such as mozjpeg or libbpg, with predictable results. Out of the few dozen pending security fixes in libtiff, the vast majority likely traces back to afl-fuzz, in part thanks to the work of Tobias Ospelt, William Robinet, and Paris Zoumpouloglou.

Compared to projects such as Mayhem, I'm particularly happy that afl-fuzz has a knack for finding complex issues in relatively tough, security-relevant targets that we actually need to get in a good shape - including security holes in IJG jpeg, libjpeg-turbo, libpng, Firefox, Internet Explorer, GnuTLS, GnuPG, unzip, or file. Heck, the fuzzer even managed to find crash-only bugs in OpenSSH and multiple non-trivial crashing SQL statements in sqlite3. On a much less serious but funny note, it also triggered an somewhat embarrassing security bug in splint, a tool for, quoth, "statically checking C programs for security vulnerabilities and coding mistakes"...

All in all, I'm very happy and humbled with the success of the tool, and how many developers are just grabbing it and running it against their projects without having to spend hours to fiddle various knobs. The afl-users@ mailing list is now 120+ members strong - and I'll do my best to keep the fuzzer useful and enjoyable to play with :-) Many feature suggestions ship in a matter of days - so if you have any ideas, be sure to send them in.

(And if you haven't looked at afl-fuzz recently, give it a try!)

January 09, 2015

afl-fuzz: making up grammar with a dictionary in hand

One of the most significant limitations of afl-fuzz is that its mutation engine is syntax-blind and optimized for compact data formats, such as binary files (e.g., archives, multimedia) or terse human-readable languages (RTF, shell scripts). Any general-purpose fuzzer will have a harder time dealing with more verbose dialects, such as SQL or HTTP. You can improve your odds in a variety of ways, and the results can be surprisingly good - but ultimately, it's never easy to get from Set-Cookie: FOO=BAR to Content-Length: -1 by randomly flipping bits.

The common wisdom is that if you want to fuzz data formats with such ornate grammars, you need to build an one-off, protocol-specific mutation engine with the appropriate syntax templates baked in. Of course, writing such code isn't easy. In essence, you need to manually build a model precise enough so that the generated test cases almost always make sense to the targeted parser - but creative enough to trigger unintended behaviors in that codebase. It takes considerable experience and a fair amount of time to get it just right.

I was thinking about using afl-fuzz to reach some middle ground between the two worlds. I quickly realized that if you give the fuzzer a list of basic syntax tokens - say, the set of reserved keywords defined in the spec - the instrumentation-guided nature of the tool means that even if we just mindlessly clobber the tokens together, we will be able to distinguish between combinations that are nonsensical and ones that actually follow the rules of the underlying grammar and therefore trigger new states in the instrumented binary. By discarding that first class of inputs and refining the other, we could progressively construct more complex and meaningful syntax as we go.

Ideas are cheap, but when I implemented this one, it turned out to be a good bet. For example, I tried it against sqlite, with the fuzzer fed a collection of keywords grabbed from the project's docs (-x testcases/_extras/sql/). Equipped with this knowledge, afl-fuzz quickly spewed out a range of valid if unusual statements, such as:

select sum(1)LIMIT(select sum(1)LIMIT -1,1); select round( -1)````; select group_concat(DISTINCT+1) |1; select length(?)in( hex(1)+++1,1); select abs(+0+ hex(1)-NOT+1) t1; select DISTINCT "Y","b",(1)"Y","b",(1); select - (1)AND"a","b"; select ?1in(CURRENT_DATE,1,1); select - "a"LIMIT- /* */ /* */- /* */ /* */-1; select strftime(1, sqlite_source_id());

(It also found a couple of crashing bugs.)

All right, all right: grabbing keywords is much easier than specifying the underlying grammar, but it still takes some work. I've been wondering how to scratch that itch, too - and came up with a fairly simple algorithm that can help those who do not have the time or the inclination to construct a proper dictionary.

To explain the approach, it's useful to rely on the example of a PNG file. The PNG format uses four-byte, human-readable magic values to indicate the beginning of a section, say:

89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 | .PNG........IHDR
00 00 00 20 00 00 00 20 02 03 00 00 00 0e 14 92 | ................

The algorithm in question can identify "IHDR" as a syntax token by piggybacking on top of the deterministic, sequential bit flips that are already being performed by afl-fuzz across the entire file. It works by identifying runs of bytes that satisfy a simple property: that flipping them triggers an execution path that is distinct from the product of flipping stuff in the neighboring regions, yet consistent across the entire sequence of bytes.

This signal strongly implies that touching any of the affected bytes causes the failure of an underlying atomic check, such as header.magic_value == 0xDEADBEEF or strcmp(name, "Set-Cookie"). When such a behavior is detected, the entire blob of data is added to the dictionary, to be randomly recombined with other dictionary tokens later on.

This second trick is not a substitute for a proper, hand-crafted list of keywords; for one, it will only know about the syntax tokens that were present in the input files, or could be synthesized easily. It will also not do much when pitted against optimized, tree-based parsers that do not perform atomic string comparisons. (The fuzzer itself can often clear that last obstacle anyway, but the process will be slow.)

Well, that's it. If you want to try out the new features, click here and let me know how it goes!