Hacker News from Y Combinator

Syndicate content
Links for the intellectually curious, ranked by readers. // via fulltextrssfeed.com
Updated: 6 hours 15 min ago

CompCert: A formally verified optimizing C compiler

6 hours 15 min ago

CompCert is a formally verified optimizing C compiler. Its intended use is the compilation of safety-critical and mission-critical software written in C and meeting high levels of assurance. It accepts most of the ISO C 99 language, with some exceptions and a few extensions. It produces machine code for the PowerPC (32-bit), ARM, and IA32 (x86 32-bit) architectures.

What sets CompCert apart?

Unlike any other production compiler, CompCert is formally verified, using machine-assisted math­ematical proofs, to be exempt from miscompilation issues. In other words, the code it produces is proved to behave exactly as specified by the semantics of the source C program.

This level of confidence in the correctness of the compilation process is unprecedented and con­tributes to meeting the highest levels of software assurance.

The formal proof covers all transformations from the abstract syntax tree to the generated assem­bly code. To preprocess and produce object and executable files, an external C pre­processor, assemblers, linkers, and C libraries have to be used. However, these unverified stages are well-understood and robust from an implementation perspective. This has been demon­strated on a development version of CompCert by a 2011 study by Regehr, Yang et al.:

“The striking thing about our CompCert results is that the middle-end bugs we found in all other compilers are absent. As of early 2011, the under-development version of CompCert is the only compiler we have tested for which Csmith cannot find wrong-code errors. This is not for lack of trying: we have devoted about six CPU-years to the task. The apparent unbreak­ability of CompCert supports a strong argument that developing compiler optimizations within a proof framework, where safety checks are explicit and machine-checked, has tangible be­ne­fits for compiler users.”

Your benefits
  • Using the CompCert C compiler is a natural complement to applying formal verification tech­niques (static analysis, program proof, model checking) at the source-code level. The correctness proof of CompCert guarantees that all safety properties verified on the source code automatically hold for the generated code as well.
  • On typical embedded processors, the code generated by CompCert typically runs twice as fast as the code generated by GCC without optimizations, and only 20% slower than GCC at optimization level 3. (Details about the benchmark mix used to obtain these numbers are available on request.)
Availability

Xavier Leroy with INRIA is the architect and lead developer of CompCert. Numerous renowned researchers have contributed ideas, code, or feedback. When in 2014 the compiler reached market-ready maturity, INRIA and AbsInt entered a license agreement to provide commercial licenses to end users.

Source code and documentation of CompCert, including the compiler proofs, can be downloaded from INRIA’s dedicated CompCert site.

For research purposes, the usage of CompCert is free of charge. AbsInt offers commercial li­censes, provides industrial-strength support and maintenance, and contributes to the advance­ment of the tool.

For further information, contact info@absint.com.

An Explanation of Type Inference for ML/Haskell

6 hours 15 min ago

Posted on February 28, 2015

Tags: sml, haskell, types

A couple of days ago I wrote a small implementation of a type inferencer for a mini ML language. It turns out there are very few explanations of how to do this properly and the ones that exist tend to be the really naive, super exponential algorithm. I wrote the algorithm in SML but nothing should be unfamiliar to the average Haskeller.

Type inference breaks down into essentially 2 components

  1. Constraint Generation
  2. Unification

We inspect the program we’re trying to infer a type for and generate a bunch of statements (constraints) which are of the form

This type is equal to this type

These types have “unification variables” in them. These aren’t normal ML/Haskell type variables. They’re generated by the compiler, for the compiler, and will eventually be filled in with either

  1. A rigid polymorphic variable
  2. A normal concrete type

They should be thought of as holes in an otherwise normal type. For example, if we’re looking at the expression

f a

We first just say that f : 'f where 'f is one of those unification variables I mentioned. Next we say that a : 'a. Since we’re apply f to a we can generate the constraints that

'f ~ 'x -> 'y 'a ~ 'x

Since we can only apply things with of the form _ -> _. We then unify these constraints to produce f : 'a -> 'x and a : 'a. We’d then using the surrounding constraints to produce more information about what exactly 'a and 'x might be. If this was all the constraints we had we’d then “generalize” 'a and 'x to be normal type variables, making our expression have the type x where f : a -> x and a : a.

Now onto some specifics

Set Up

In order to actually talk about type inference we first have to define our language. We have the abstract syntax tree:

type tvar = int local val freshSource = ref 0 in fun fresh () : tvar = !freshSource before freshSource := !freshSource + 1 end datatype monotype = TBool | TArr of monotype * monotype | TVar of tvar datatype polytype = PolyType of int list * monotype datatype exp = True | False | Var of int | App of exp * exp | Let of exp * exp | Fn of exp | If of exp * exp * exp

First we have type variables which are globally unique integers. To give us a method for actually producing them we have fresh which uses a ref-cell to never return the same result twice. This is probably surprising to Haskellers: SML isn’t purely functional and frankly this is less noisy than using something like monad-gen.

From there we have mono-types. These are normal ML types without any polymorphism. There are type/unification variables, booleans, and functions. Polytypes are just monotypes with an extra forall at the front. This is where we get polymorphism from. A polytype binds a number of type variables, stored in this representation as an int list. There is one ambiguity here, when looking at a variable it’s not clear whether it’s supposed to be a type variable (bound in a forall) and a unification variable. The idea is that we never ever inspect a type bound under a forall except when we’re converting it to a monotype with fresh unification variables in place of all of the bound variables. Thus, when inferring a type, every variable we come across is a unification variable.

Finally, we have expressions. Aside form the normal constants, we have variables, lambdas, applications, and if. The way we represent variables here is with DeBruijn variables. A variable is a number that tells you how many binders are between it and where it was bound. For example, const would be written Fn (Fn (Var 1)) in this representation.

With this in mind we define some helpful utility functions. When type checking, we have a context full of information. The two facts we know are

datatype info = PolyTypeVar of polytype | MonoTypeVar of monotype type context = info list

Where the ith element of a context indicates the piece of information we know about the ith DeBruijn variable. We’ll also need to substitute a type variable for a type. We also want to be able to find out all the free variables in a type.

fun subst ty' var ty = case ty of TVar var' => if var = var' then ty' else TVar var' | TArr (l, r) => TArr (subst ty' var l, subst ty' var r) | TBool => TBool fun freeVars t = case t of TVar v => [v] | TArr (l, r) => freeVars l @ freeVars r | TBool => []

Both of these functions just recurse over types and do some work at the variable case. Note that freeVars can contain duplicates, this turns out not to be important in all cases except one: generalizeMonoType. The basic idea is that given a monotype with a bunch of unification variables and a surrounding context, figure out which variables can be bound up in a polymorphic type. If they don’t appear in the surrounding context, we generalize them by binding them in a new poly type’s forall spot.

fun dedup [] = [] | dedup (x :: xs) = if List.exists (fn y => x = y) xs then dedup xs else x :: dedup xs fun generalizeMonoType ctx ty = let fun notMem xs x = List.all (fn y => x <> y) xs fun free (MonoTypeVar m) = freeVars m | free (PolyTypeVar (PolyType (bs, m))) = List.filter (notMem bs) (freeVars m) val ctxVars = List.concat (List.map free ctx) val polyVars = List.filter (notMem ctxVars) (freeVars ty) in PolyType (dedup polyVars, ty) end

Here the bulk of the code is deciding whether or not a variable is free in the surrounding context using free. It looks at a piece of info to determine what variables occur in it. We then accumulate all of these variables into cxtVars and use this list to decide what to generalize.

Next we need to take a polytype to a monotype. This is the specialization of a polymorphic type that we love and use when we use map on a function from int -> double. This works by taking each bound variable and replacing it with a fresh unification variables. This is nicely handled by folds!

fun mintNewMonoType (PolyType (ls, ty)) = foldl (fn (v, t) => subst (TVar (fresh ())) v t) ty ls

Last but not least, we have a function to take a context and a variable and give us a monotype which corresponds to it. This may produce a new monotype if we think the variable has a polytype.

exception UnboundVar of int fun lookupVar var ctx = case List.nth (ctx, var) handle Subscript => raise UnboundVar var of PolyTypeVar pty => mintNewMonoType pty | MonoTypeVar mty => mty

For the sake of nice error messages, we also throw UnboundVar instead of just subscript in the error case. Now that we’ve gone through all of the utility functions, on to unification!

Unification

A large part of this program is basically “I’ll give you a list of constraints and you give me the solution”. The program to solve these proceeds by pattern matching on the constraints.

In the empty case, we have no constraints so we give back the empty solution.

fun unify [] = []

In the next case we actually have to look at what constraint we’re trying to solve.

| unify (c :: constrs) = case c of

If we’re lucky, we’re just trying to unify TBool with TBool, this does nothing since these types have no variables and are equal. In this case we just recurse.

(TBool, TBool) => unify constrs

If we’ve got two function types, we just constrain their domains and ranges to be the same and continue on unifying things.

| (TArr (l, r), TArr (l', r')) => unify ((l, l') :: (r, r') :: constrs)

Now we have to deal with finding a variable. We definitely want to avoid adding (TVar v, TVar v) to our solution, so we’ll have a special case for trying to unify two variables.

| (TVar i, TVar j) => if i = j then unify constrs else addSol i (TVar j) (unify (substConstrs (TVar j) i constrs))

This is our first time actually adding something to our solution so there’s several new elements here. The first is this function addSol. It’s defined as

fun addSol v ty sol = (v, applySol sol ty) :: sol

So in order to make sure our solution is internally consistent it’s important that whenever we add a type to our solution we first apply the solution to it. This ensures that we can substitute a variable in our solution for its corresponding type and not worry about whether we need to do something further. Additionally, whenever we add a new binding we substitute for it in the constraints we have left to ensure we never have a solution which is just inconsistent. This prevents us from unifying v ~ TBool and v ~ TArr(TBool, TBool) in the same solution! The actual code for doing this is that substConstr (TVar j) i constrs bit.

The next case is the general case for unifying a variable with some type. It looks very similar to this one.

| ((TVar i, ty) | (ty, TVar i)) => if occursIn i ty then raise UnificationError c else addSol i ty (unify (substConstrs ty i constrs))

Here we have the critical occursIn check. This checks to see if a variable appears in a type and prevents us from making erroneous unifications like TVar a ~ TArr (TVar a, TVar a). This occurs check is actually very easy to implement

fun occursIn v ty = List.exists (fn v' => v = v') (freeVars ty)

Finally we have one last case: the failure case. This is the catch-all case for if we try to unify two things that are obviously incompatible.

| _ => raise UnificationError c

All together, that code was

fun applySol sol ty = foldl (fn ((v, ty), ty') => subst ty v ty') ty sol fun applySolCxt sol cxt = let fun applyInfo i = case i of PolyTypeVar (PolyType (bs, m)) => PolyTypeVar (PolyType (bs, (applySol sol m))) | MonoTypeVar m => MonoTypeVar (applySol sol m) in map applyInfo cxt end fun addSol v ty sol = (v, applySol sol ty) :: sol fun occursIn v ty = List.exists (fn v' => v = v') (freeVars ty) fun unify ([] : constr list) : sol = [] | unify (c :: constrs) = case c of (TBool, TBool) => unify constrs | (TVar i, TVar j) => if i = j then unify constrs else addSol i (TVar j) (unify (substConstrs (TVar j) i constrs)) | ((TVar i, ty) | (ty, TVar i)) => if occursIn i ty then raise UnificationError c else addSol i ty (unify (substConstrs ty i constrs)) | (TArr (l, r), TArr (l', r')) => unify ((l, l') :: (r, r') :: constrs) | _ => raise UnificationError c Constraint Generation

The other half of this algorithm is the constraint generation part. We generate constraints and use unify to turn them into solutions. This boils down to two functoins. The first is to glue together solutions.

fun <+> (sol1, sol2) = let fun notInSol2 v = List.all (fn (v', _) => v <> v') sol2 val sol1' = List.filter (fn (v, _) => notInSol2 v) sol1 in map (fn (v, ty) => (v, applySol sol1 ty)) sol2 @ sol1' end infixr 3 <+>

Given two solutions we figure out which things don’t occur in the in the second solution. Next, we apply solution 1 everywhere in the second solution, giving a consistent solution wihch contains everything in sol2, finally we add in all the stuff not in sol2 but in sol1. This doesn’t check to make sure that the solutions are actually consistent, this is done elsewhere.

Next is the main function here constrain. This actually generates solution and type given a context and an expression. The first few cases are nice and simple

fun constrain ctx True = (TBool, []) | constrain ctx False = (TBool, []) | constrain ctx (Var i) = (lookupVar i ctx, [])

In these cases we don’t infer any constraints, we just figure out types based on information we know previously. Next for Fn we generate a fresh variable to represent the arguments type and just constrain the body.

| constrain ctx (Fn body) = let val argTy = TVar (fresh ()) val (rTy, sol) = constrain (MonoTypeVar argTy :: ctx) body in (TArr (applySol sol argTy, rTy), sol) end

Once we have the solution for the body, we apply it to the argument type which might replace it with a concrete type if the constraints we inferred for the body demand it. For If we do something similar except we add a few constraints of our own to solve.

| constrain ctx (If (i, t, e)) = let val (iTy, sol1) = constrain ctx i val (tTy, sol2) = constrain (applySolCxt sol1 ctx) t val (eTy, sol3) = constrain (applySolCxt (sol1 <+> sol2) ctx) e val sol = sol1 <+> sol2 <+> sol3 val sol = sol <+> unify [ (applySol sol iTy, TBool) , (applySol sol tTy, applySol sol eTy)] in (tTy, sol) end

Notice how we apply each solution to the context for the next thing we’re constraining. This is how we ensure that each solution will be consistent. Once we’ve generated solutions to the constraints in each of the subterms, we smash them together to produce the first solution. Next, we ensure that the subcomponents have the right type by generating a few constraints to ensure that iTy is a bool and that tTy and eTy (the types of the branches) are both the same. We have to carefully apply the sol to each of these prior to unifying them to make sure our solution stays consistent.

This is practically the same as what the App case is

| constrain ctx (App (l, r)) = let val (domTy, ranTy) = (TVar (fresh ()), TVar (fresh ())) val (funTy, sol1) = constrain ctx l val (argTy, sol2) = constrain (applySolCxt sol1 ctx) r val sol = sol1 <+> sol2 val sol = sol <+> unify [(applySol sol funTy, applySol sol (TArr (domTy, ranTy))) , (applySol sol argTy, applySol sol domTy)] in (ranTy, sol) end

The only real difference here is that we generate different constraints: we make sure we’re applying a function whose domain is the same as the argument type.

The most interesting case here is Let. This implements let generalization which is how we actually get polymorphism. After inferring the type of the thing we’re binding we generalize it, giving us a poly type to use in the body of let. The key to generalizing it is that generalizeMonoType we had before.

| constrain ctx (Let (e, body)) = let val (eTy, sol1) = constrain ctx e val ctx' = applySolCxt sol1 ctx val eTy' = generalizeMonoType ctx' (applySol sol1 eTy) val (rTy, sol2) = constrain (PolyTypeVar eTy' :: ctx') body in (rTy, sol1 <+> sol2) end

We do pretty much everything we had before except now we carefully ensure to apply the solution we get for the body to the context and then to generalize the type with respect to that new context. This is how we actually get polymorphism, it will assign a proper polymorphic type to the argument.

That wraps up constraint generation. Now all that’s left to see if the overall driver for type inference.

fun infer e = let val (ty, sol) = constrain [] e in generalizeMonoType [] (applySol sol ty) end end

So all we do is infer and generalize a type! And there you have it, that’s how ML and Haskell do type inference.

Wrap Up

Hopefully that clears up a little of the magic of how type inference works. The next challenge is to figure out how to do type inference on a language with patterns and ADTs! This is actually quite fun, pattern checking involves synthesizing a type from a pattern which needs something like linear logic to handle pattern variables correctly.

With this we’re actually a solid 70% of the way to building a type checker to SML. Until I have more free time though, I leave this as an exercise to the curious reader.

Cheers,

Please enable JavaScript to view the comments powered by Disqus.

comments powered by

Ibash notebook

6 hours 15 min ago

Did you know that there's a Bash kernel for IPython Notebook? It even displays inline images. To give you a glimpse, the code cell below makes an API call to memegenerator.net, which generates images on demand. From the response, the URL of the generated image is extracted using jq and subsequently downloaded using curl. The output is then displayed as an inline image by piping it to a function called display. Perhaps a bit contrived, but if not with a meme, how else am I supposed to grab your attention these days?

In this post, I first give some background on notebooks and the IPython Notebook/Jupyter project. Then, I explore the idea whether this "IBash Notebook" has the potential to become a convenient environment for doing data science. Subsequently, I explain how I added support for displaying inline images. As an aside, I wonder whether it would be feasible and worthwhile to publish my book Data Science at the Command Line as a collection of notebooks. Finally, I discuss which issues remain to be improved and how you can try out IBash Notebook for yourself. I'm curious to hear what you think.

You get a notebook. And you get a notebook. Everybody gets a notebook!

Let's take a step back for a moment. Doing research is hard. Recalling which steps you've taken, and why, is even harder. To be an effective researcher, you may want to keep a laboratory notebook. Besides having a record of your steps and results, this also allows you to improve reproducibility, share your research with others, and, yes, think more clearly. So, why wouldn't you keep a notebook?

Well, if you perform your research or analysis on a computer, where most steps boil down to running code, invoking commands, and clicking buttons, keeping an analogue notebook is rather cumbersome. Fortunately, since recently, digital counterparts are quickly gaining popularity. For the R community, for example, there's R Markdown. And for those who use the Python scientific stack, there's IPython Notebook. Both solutions are free and allow you to combine code, text, equations, and visualizations into a single document.

The people behind the IPython project saw the potential of having a language-agnostic architecture. By creating a flexible messaging protocol, writing good documentation for it, and rebranding the project as the Jupyter project, they opened the door to other languages. And now, languages like Julia, Ruby, and Haskell have their own kernel. Beaker, a completely different project, even supports multiple languages in the same notebook.

What about poor old Bash?

To demonstrate how easy it is to create a new kernel for IPython Notebook, Thomas Kluyver created a Python package called bash_kernel. This Bash kernel basically works by using pexpect to wrap around a Bash command line. When I stumbled upon this package I immediately got excited. This could be much more than just a demonstration. Call me crazy, but I believe that with some additional effort, we might have an IBash Notebook that would have some important advantages over a terminal (which is the standard environment to interact with the command line; see image below).

First, and perhaps most importantly, the command line is ad-hoc in nature, which makes it difficult to reproduce your steps or share them with your peers. To improve reproducibility, you could put those steps in a shell script, Makefile, or Drakefile, but when you're working in a notebook, they would be stored automatically.

Second, if you're running a server or virtual machine, there would be no need to ssh into it. As a result, Microsoft Windows users wouldn't need to resort to a third-party tool like PuTTY anymore. I'm particularly interested in this advantage, together with the next two, because ever since I started writing Data Science at the Command Line, I've been looking for ways to make the command line more accessible to newcomers.

Third, for users who are new to the command line, a notebook with code cells could be less intimidating than a terminal with a prompt. Because the browser (and perhaps also IPython Notebook) is a familiar environment, the threshold to try out the command line will be lower.

Fourth, in order to view an image located on a server or virtual machine, you normally have to go trough an extra hoop. Approaches that I know of are either: (1) copy this image to the host OS, (2) forward X11, or (3) serve it using, say, python -m SimpleHTTPServer and then open it in a browser. With a notebook, images can be shown inline. Which brings us to...

Adding support for displaying inline images

For the Bash kernel to be a convenient environment for doing data science, it could use a few additional features besides running commands. Thanks to the architecture of IPython Notebook, inline Markdown and LaTeX equations work out of the box. Having seen Gate One (a browser-based terminal that I had running on 200 EC2 instances for my workshop at Strata NYC) and pigshell (a shell-like website that lets you interact with various APIs as Unix files), which are both able to display inline images, I knew that's what the Bash kernel needed next.

I initially thought this would be as easy as detecting the MIME type of the output of a command. That way, when you would run cat file.png, an image would be shown automatically. Unfortunately this approach didn't work because, as I later learned, pexpect isn't meant to transfer binary data. With some suggestions from Thomas Kluyver, I implemented the following solution instead. (You may decide whether it's a hack or not.)

The solution includes a Bash function called display that is registered when the kernel starts. That way, images can now be displayed by running something as simple as:

or something as involved as:

cat iris.csv | # Read our beloved Iris data set cols -C species body tapkee -m pca | # Apply PCA using tapkee header -r x,y,species | # Replace header of CSV Rio-scatter x y species | display # Create scatter plot using ggplot2

which produces:

In case you're interested, cols and body are used to only pass numerical columns and no header to tapkee, which is a fantastic library for dimensionality reduction by Sergey Lisitsyn. These two Bash scripts, together with header and Rio-scatter, can be found in this repository. Speaking of command-line tools for plotting, Bokeh, which is a Python visualization library built on top of matplotlib, will soon have its own command-line tool as well.

To see what the display function looks like, we can run type display in a notebook:

display is a function display () { TMPFILE=$(mktemp ${TMPDIR-/tmp}/bash_kernel.XXXXXXXXXX); cat > $TMPFILE; echo "bash_kernel: saved image data to: $TMPFILE" 1>&2 }

In words, display saves the standard input to a temporary file and prints the filename to standard error. After a code cell has been evaluated, the Bash kernel simply extracts the filename from the output, detects its MIME type using the imghdr library, and sends the image data (encoded with base64) to the front end. Easy peasy.

I chose the name "display" because there's also a command-line tool in ImageMagick called "display" that accepts image data from standard input and shows it in a new window. Because that tool works only when X is running, I figured that a function called "display" could serve as a drop-in replacement when using IPython Notebook.

Aside: Publishing a book as a collection of notebooks

IPython Notebook can also be used to write entire books. Mining the Social Web, Probabilistic Programming and Bayesian Methods for Hackers, and Python for Signal Processing are but a few examples of books that have been published as a collection of notebooks (usually one notebook per chapter). The main advantage of a notebook as opposed to a book is that you can immediately run the code yourself. Instead of passively reading about a certain package or tool, you can actively try it out.

I wonder if I could (and should) do the same with my book Data Science at the Command Line. As an initial test, I manually converted part of the first chapter to a notebook, which you can view on nbviewer. Converting the book's source code wouldn't be too difficult, especially if we to convert it to Markdown and use ipymd. What would be more challenging are packaging and distribution.

The book introduces over 80 command-line tools, and installing them manually would take the better part of a day. I do offer a virtual machine based on Vagrant and VirtualBox that has everything installed, but I suspect there's a better way to package this with IBash Notebook. For example, recently, Thomas Wiecki created a Docker container that launches an IPython notebook server with the PyData stack installed. And the tmpnb project seems very promising as well. I must admit that I haven't had time to look into Docker and these two projects at all.

Distribution is then something I would need to figure out with my publisher O'Reilly Media. Considering the recent efforts for the book Just Enough Math by Andew Odewahn, O'Reilly's CTO, and their forward thinking regarding publishing in general, I foresee many opportunities.

What's next?

Having inline Markdown, equations, and images sure is nice. However, in my opinion, the Bash kernel currently has two issues that hamper usability. First, the output is only printed when the command is finished; there are no real-time updates. This is especially inconvenient if you want to keep an eye on some long-running process using, say, tail -f or htop. Second, there's no interactivity with the process possible. This means that you cannot drop into some other REPL like julia or psql. If there's sufficient interest in IBash Notebook, then I suspect that these issues can be solved. Regardless, I believe that despite these two issues, IBash Notebook could very well serve as a means to introduce people to the command line.

If you want to try out the Bash kernel for yourself, you should install IPython 3 (which is currently in development). Then, you can clone the Bash kernel GitHub repository and install the package. (Best to do this all inside a virtual environment.) Next time you start a new notebook, you should be able to select the Bash kernel in the top-right corner.

So, what do you think? Do you agree that IBash Notebook has potential? Am I crazy thinking that the command line can ever live outside the terminal? Would you like to see my book published as a collection of IBash notebooks? So many questions. Let me know on Twitter.

Cheers,

Jeroen

Thanks to Rob Doherty and Adam Johnson for reading drafts of this.

Chip Makers Will Merge in Deal Worth $11.8B

6 hours 15 min ago

NXP Semiconductors said on Sunday that it would buy a smaller peer, Freescale Semiconductor, in an $11.8 billion deal that would create a big maker of chips for industries as varied as automobiles and mobile payments.

The merger will also offer some relief to the private equity firms that bought Freescale at the height of the leveraged buyout boom, only to see the financial crisis bring the company low.

A combination would help the two chip manufacturers in their dealings with customers like car companies and phone makers that are looking to consolidate their lists of suppliers. 

In fall 2013, Applied Materials, an American manufacturer of chip-making equipment, acquired Japanese rival Tokyo Electron for more than $9 billion. Other semiconductor companies, like Qualcomm and Infineon Technologies, have also struck deals, in part to gain greater negotiating leverage.

Both NXP and Freescale have also benefited from a recent boom, as companies of all stripes look to add networking capabilities to their products. NXP in particular has had a surge in demand for so-called near-field communications technology that lets phones — notably the iPhone 6 — interact wirelessly with equipment like payment terminals.

Together, NXP, which has its headquarters in the Netherlands, and Freescale, which is based in Austin, Tex., reported $10.6 billion in sales last year.

“The combination of NXP and Freescale creates an industry powerhouse focused on the high-growth opportunities in the smarter world,” Richard L. Clemmer, NXP’s chief executive, said in a statement. “We fully expect to continue to significantly outgrow the overall market, drive world-class profitability and generate even more cash, which taken together will maximize value for both Freescale and NXP shareholders.”

Under the deal’s terms, NXP will pay $6.25 a share in cash and 0.3521 of one of its shares for each Freescale share held. That values Freescale at roughly its existing market capitalization, although shares of Freescale rose last month after The New York Post reported that the company was exploring a sale.

The discussions between the two companies that eventually led to the current deal began a little over six months ago, according to people briefed on the matter, though potential strategic acquirers of Freescale had made inquiries about a deal several times over the past four years.

Both NXP and Freescale were previously parts of bigger corporations that eventually became targets of private equity firms. NXP was formerly a division of the Dutch electronics giant Philips until it was acquired in 2006 by a group led by Kohlberg Kravis Roberts and Bain Capital for about $10 billion.

Freescale had been a part of Motorola until being purchased in 2006 by the Blackstone Group, the Carlyle Group, TPG Capital and Permira for $17.6 billion, including the assumption of debt.

Both companies soon began to struggle under new ownership, burdened by new and huge debt obligations and falling demand during the financial crisis. Freescale in particular suffered from an economic downturn and the loss of its biggest customer, its former parent. 

During its darkest days, Freescale’s earnings before interest, taxes, depreciation and amortization, or Ebitda, plummeted around 80 percent. And its ratio of debt to Ebitda swelled to 13 times. 

Faced with potentially needing to put the chip maker into bankruptcy, the company’s private equity owners slashed costs, shook up management and revamped its product portfolio, according to people with direct knowledge of the matter.

The fortunes of the two companies have improved since going public. Since an initial public offering in the summer of 2010, NXP’s shares have leaped 506 percent, closing on Friday at $84.90. Freescale’s stock has doubled since returning to the public markets in June 2011, closing at $36.11.

But with $1 billion in new debt to finance the deal, the combined company will be maintaining a heavy debt load of some $9.5 billion.

At the initial deal price, Freescale’s private equity backers will roughly recoup their initial investment. But the private equity firms are betting that cost savings of about $500 million from merging the two manufacturers will propel the stock price of the combined company.

A version of this article appears in print on March 2, 2015, on page B6 of the New York edition with the headline: Chip Makers Will Merge In Deal Worth $11.8 Billion.

Notes on watching "Aliens" for the first time again, with a bunch of kids

6 hours 15 min ago

Matt Zoller Seitz is the Editor-in-Chief of RogerEbert.com, TV critic for New York Magazine, the creator of many video essays about film history and style, a finalist for the Pulitzer Prize in criticism, and the author of The Wes Anderson Collection. His writing on film and TV has appeared in The New York Times, Salon, New York Press, The Star-Ledger and Dallas Observer. (Banner illustration by Max Dalton)

March 1, 2015   |   Print Page

For his 11th birthday, my son asked if he could have a slumber party. He invited seven other fifth-grade boys. They played video games for a couple of hours, ate pizza, then said they wanted to watch a movie. They'd seen every comic book movie multiple times. Seen all the Indiana Jones films. Star Wars. Anything with a hobbit in it. The usual 11-year old boy options, circa 2015, weren't going to work. 

So I suggested "

They agreed (some of them had seen the first one anyway, and nearly all had seen at least one film with a xenomorph in it) and so we watched it together. And as we watched, I realized again that while unfortunately you can't see a great movie again for the first time, the next-best thing is to show it to people who've never seen it.

My first time with James Cameron's sci-fi war movie was a great filmgoing experience. I saw "Aliens" at the NorthPark 1 and 2 theater at NorthPark Mall in my hometown of Dallas, with a high school classmate who was, at that time, my regular action movie-watching buddy: Gabe Michaels. We drove to NorthPark to catch the 11 a.m. show on opening day and got in line a couple of hours early. We'd already drunk a bit of soda beforehand and I think we might have downed some more while standing in line. When we got into the theater, they seated us immediately and there was only one preview, for "The Fly," and then wham, they started the movie. Neither Gabe nor I nor anyone else who'd been standing in that line wanted to get up from our seats and answer nature's call, even though we all pretty desperately had to; there was a lot of muttering and shifting in seats, quite a few "grin and bear it" expressions. 

If you've seen the film, you know there are no aliens to speak of for the first hour, then suddenly there are aliens all over the place, coming out of the walls and ceiling, drooling and shrieking and dragging Marines off into the darkness to be cocooned. It's one of the greatest releases of built-up tension in action film history. Throughout this sequence the audience was enthralled, screaming as the xenomorphs attacked, cheering as Ripley took control of the all-terrain vehicle to rescue the imperiled Colonial Marines. Then when the ATV crashed through the wall, the music stopped, and Hicks told her she'd blown the trans-axle and need to "ease down, Ripley, ease down," everyone collectively seemed to realize they were being given a breather, so at that point Gabe and I and probably a fifth of the audience rose from our seats and headed for the bathrooms: fast-walking, some running.

Guys at the urinals were peeing as fast as they could because they didn't want to miss another minute of "Aliens." You'd have thought somebody was timing them. Like this was the Olympic qualifying round for the bladder evacuation team. But they weren't going fast enough to suit a guy standing near the front door of men's room. He yelled,  "Goddammit! All of you, PISS FASTER!!!" Everyone cracked up. 

And that's when I knew "Aliens" was going to be a hit.

Anyway, the slumber party: all the kids seemed to agree that "Aliens" was a good suggestion because even though it had aliens in it, it wasn't just trying to scare you, like the first "Guardians of the Galaxy," "Dr. Who," and (for some reason) "Saturday Night Live." We watched it anyway. It went over well. 

The biggest challenge was dissuading kids from trying to predict every single thing that was going to happen. This is a generation of talkers. They have to comment on everything. No thought can go unexpressed. Maybe this was true when I was a kid as well (I honestly don't remember), but rather than endlessly correct them I decided to just roll with it, exercising my slumber party guardian veto power during scenes that I felt pretty sure would enthrall them if they would just shut up for five minutes (I was rarely proved wrong in my guesses). But it was a sharp crowd, and for the most part the movie went over quite well, for an analog-era science fiction spectacular that's turning 30 next year. 

One boy said that Ripley in her hyper sleep chamber looked like Sleeping Beauty. As this was an intentional reference on writer-director James Cameron's part (there's a Snow White reference an hour later) this seemed like a promising note on which to begin the screening. My son's friend Henry said, "I like the way this looks. It's futuristic but it's old school. It's almost steampunk." "This is like Team Fortress 2," a boy remarked. "Dude, shut up, this was made like 20 years before Team Fortress 2," said the kid next to him. "This is, like, every science fiction movie ever made," another said, as Ripley operated the power loader for the first time. 

"This movie has so many cliches in it," a boy said when Colonial Marines disembarked the drop ship and made their way through dark, rainy wind to enter the alien-infested colony. My son told him, "This movie was made in 1986. It invented all the cliches." Another one of his friends was impressed by the "personal data transmitters" implanted in the colonists—impressed that someone had thought of that way back in 1986.

The first big jump of the night was the face hugger in the tank trying to "kiss" the evil yuppie Burke. All eight kids flipped out. One screamed. Second big jump of the night: the "please kill me" woman. Half the boys were watching her through the cracks between their fingers. 

They liked Ripley, Hicks, Frost, Apone, Bishop the android, and even Hudson, whose defeatism irritated them so much that I think they would've hated him if he weren't so funny. "Somebody shoot that guy," one said. Frost insisting that "it doesn't matter" when the "poontang" is Arcturian confused a couple of kids. "It means he's bisexual," one explained. The cigar-chewing Sgt. Apone's oddly musical phrase "assholes and elbows" got the biggest laugh of the evening; two hours and twenty minutes later, the kids were quoting it as they brushed their teeth. Frost's quip, "What are we supposed to use, man, harsh language?" made my son laugh for nearly a full minute.  

During the final alien assault (where they come through the ceiling panels!) a boy half-hidden under blanket said, "I would commit suicide if I were in this position." 

Vasquez was the MVP of the movie. I think all eight boys might have a little bit of a crush on Vasquez. When she shot the alien under her boot, one exclaimed his delight with profanity, then immediately apologized to me for it. Another boy said Vasquez reminded him of "this lady who works at Costco." He didn't say which Costco. There was a of applause for Lt. Gorman and Vasquez holding hands as they blew themselves up. ("She died like a boss," one said.)

There was general agreement amongst the boys that they would like to see a separate film of Newt surviving for weeks on the planet full of aliens. The final duel between the queen mother alien and Ripley in her power loader was a big hit. the boys applauded both combatants' tactics, especially Ripley blocking the queen's tongue-mouth jabs with a blowtorch. ("This is like boxing, except it's slower and they're both wearing armor.")

At bedtime there was some discussion of whether an army of predators could beat an army of aliens. The issue was never resolved. The boys had trouble settling down because every few minutes somebody would plant a palm on somebody's face or grab a toe. At one point, post-screening discussion was hijacked by a science minded boy  describing his idea for an "acid-proof Colonial Marine uniform." 

"There could be face huggers hiding under the couch right now," one said after a while. There was laughter at this. Then silence. Then a stray nervous chuckles. Then a longer silence.  The boy who earlier had suggested alternatives to "Aliens" asked the first boy to "just shut up about the face huggers." 

I very rarely wish I could be 11 again, but for these kids, I'm making an exception.  

Popular Blog Posts Who do you read? Good Roger, or Bad Roger? Roger Ebert

This message came to me from a reader named Peter Svensland. He and a fr...

“Evil Against Evil”: The Fascinating Incoherence of American Sniper Niles Schwartz

On how Clint Eastwood's "American Sniper" examines evil.

Now, "Voyager": in praise of the Trekkiest "Trek" of all Ian Grey

As we mourn Abrams’ macho Star Trek obliteration, it’s a good time to revisit that most Star Trek-ian of accomplishme...

Observations of an Awards Season Skeptic, Part 4: Green Card Blues Glenn Kenny

Glenn Kenny comments on awards season, Sean Penn, Neil Patrick Harris, and the actual Oscars.

Popular Reviews Birdman The Great Gatsby Citizenfour The Salvation

Please enable JavaScript to view the comments powered by Disqus.

comments powered by MZS Archives Also from MZS Maps to the Stars Stick Figure Cinema, by Damian Arlyn Other Blogs

Roger Ebert became film critic of the Chicago Sun-Times in 1967. He is the only film critic with a star on Hollywood Walk of Fame and was named honorary life member of the Directors' Guild of America. He won the Lifetime Achievement Award of the Screenwriters' Guild, and honorary degrees from the American Film Institute and the University of Colorado at Boulder.

Chaz is the Publisher of RogerEbert.com and a regular contributor to the site, writing about film, festivals, politics, and life itself.

Our Far-Flung Correspondents are cinephiles from all over the world, hand-picked by Roger Ebert to write about movies from their unique international perspectives. They include contributors from (alphabetically) Brazil, Canada, Egypt, Great Britain, India, Mexico, the Philippines, South Korea, Turkey and the U.S. They converge every year at Ebertfest.

Tom Shales served as TV critic of The Washington Post for 25 years, winning the Pulitzer Prize for criticism in 1989. He left the once-proud paper in Ruins. Shales also spent two decades reviewing movies for NPR's Morning Edition and is the coauthor of two bestsellers: "Live from New York," on "Saturday Night Live," and "Those Guys Have All the Fun," on ESPN. No wonder he's tired.

Named after the David Cronenberg film, this is the blog of former RogerEbert.com editor Jim Emerson, where he has chronicled his enthusiasms and indulged his whims since 2005. Favorite subjects include evidence-based movie criticism, cinematic form and style, comedy, logical reasoning, language, journalism, technology, epistemology and fun. No topic is off-limits, but critical thinking is required.

In Theaters

Advertisement

Subscribe to our mailing list

Advertisement

The Ebert Club is our hand-picked selection of content for Ebert fans. You will receive a weekly newsletter full of movie-related tidbits, articles, trailers, even the occasional streamable movie. Club members also get access to our members-only section on RogerEbert.com

Advertisement

Coding is not the new literacy

6 hours 15 min ago

Despite the good intentions behind the movement to get people to code, both the basic premise and approach are flawed. The movement sits on the idea that "coding is the new literacy," but that takes a narrow view of what literacy really is.

If you ask google to define literacy it gives a mechanical definition:

the ability to read and write.

This is certainly accurate, but defining literacy as interpreting and making marks on a sheet of paper is grossly inadequate. Reading and writing are the physical actions we use to employ something far more important: external, distributable storage for the mind. Being literate isn't simply a matter of being able to put words on the page, it's solidifying our thoughts such that they can be written. Interpreting and applying someone else's thoughts is the equivalent for reading. We call these composition and comprehension. And they are what literacy really is.

Coding is not the fundamental skill

When we say that coding is the new literacy, we're arguing that wielding a pencil and paper is the old one. Coding, like writing, is a mechanical act. All we've done is upgrade the storage medium. Writing if statements and for loops is straightforward to teach people, but it doesn't make them any more capable. Just like writing, we have to know how to solidify our thoughts and get them out of our head. In the case of programming though, if we manage to do that in a certain way, a computer can do more than just store them. It can compute with them.

Reading and writing gave us external and distributable storage. Coding gives us external and distributable computation. It allows us to offload the thinking we have to do in order to execute some process. To achieve this, it seems like all we need is to show people how to give the computer instructions, but that's teaching people how to put words on the page. We need the equivalent of composition, the skill that allows us to think about how things are computed. This time, we're not recording our thoughts, but instead the models of the world that allow us to have thoughts in the first place.

We build mental models of everything - from how to tie our shoes to the way macro-economic systems work. With these, we make decisions, predictions, and understand our experiences. If we want computers to be able to compute for us, then we have to accurately extract these models from our heads and record them. Writing Python isn't the fundamental skill we need to teach people. Modeling systems is.

Modeling is the new literacy

In the same way that composition and comprehension are not tied to paper, modeling is not tied to computers. It can be both physical and mental. It takes place on paper and in Excel or with Legos and balsa wood airplanes. It is an incredibly powerful skill which we can make even greater use of by transposing our models to computers. To understand how we do that, we have to look more deeply at what it means to model.

Modeling is creating a representation of a system (or process) that can be explored or used.

This definition encompasses a few skills, but the most important one is specification. In order to represent a system, we have to understand what it is exactly, but our understanding is mired in assumptions. A fun illustration of this is the first time my co-founder, Robert, was trying to sort a list of names and getting frustrated with it. I asked him a simple question: "What does it actually mean to alphabetize something?" He had never once considered what that really meant. It was some vague concept that he had a mental model for, but he had never been forced to specify the exact result (for example, what do we do with non-English characters?).1

Defining a system or process requires breaking it down into pieces and defining those, which can then be broken down further. It is a process that helps acknowledge and remove ambiguity and it is the most important aspect of teaching people to model. In breaking parts down we can take something overwhelmingly complex and frame it in terms that we understand and actions we know how to do. The parallel to programming here is very apparent: writing a program is breaking a system down until you arrive at ideas that a computer understands and actions it knows how to do. In either case, we have to specify our system and we do that through a process of iterative crafting.

Creation is exploration

We create models by crafting them out of material.2 Sometimes our material is wood, metal, or plastic. Other times it's data or information from our senses. Either way, we start our models with a medium that we mold. This helps us escape the trap of the blank page - by starting with a hunk of clay (or data, or some physical motion, or Legos...) we don't have to imagine the leap from nothingness to something. Instead, we can get to work by manipulating what's in front of us. We can hone, and whittle, and bend, and pull apart, and glue. We can shape it as we see fit.

The process of creating a model is an act of discovery - we find out what pieces we need as we shape our material. This means we needn't fully specify a system to get started, we can simply craft new pieces as we go. We end up exploring the system as we create it and don't have to get a "complete" model to gain value. We can simply tinker. We can shave a little off or glue a some on to see what happens. And along the way, we bolster our intuition of how systems behave.

Exploration is understanding

Physical modeling teaches us the value of being able to take things apart, whether that's removing every single screw and laying the whole engine block out on the garage floor or just removing the alternator and having a look. By pulling something apart we can directly explore what makes it up. This is why interfaces in movies like Iron Man are so compelling - they allow us to just dive in.

Imagine what we could learn if we had the ability to break anything down, to reach inside it, and see what that little bit there does. The more ways we find to represent systems such that we retain that ability, the more power we will have to understand complex things.

We gain understanding through exploration, through fiddling with models and "playing them out" to see what happens. We can make our wheels bigger or plug in a different number for the interest rate and simulate the result. Through this process, we experience and imagine things we might not otherwise be able to, and the more experiences we have, the more we understand how the world works.

Digital freedom

While properties of physical modeling are useful to us as guiding principles, the digital world offers us an opportunity to step out of their limitations. We can freely create copies of parts or craft many different versions of them. We can make changes to individual pieces and the system will adapt to them. We can simulate our models in different contexts, while sophisticated tools verify our expectations. By transposing our models to a computer, we can offload the work necessary to change, simulate, and verify. We can even have our models suggest actions and let other systems perform them for us. As such, we free ourselves to explore without every change requiring us to hit the metaphorical machine shop.

There are a number of tools that already help us do this - from Matlab to Quartz Composer - but Excel is unquestionably the king. Through Excel we can model any system that we can represent as numbers on a grid, which it turns out, is a lot of them. We have modeled everything from entire businesses to markets to family vacations. Millions of people are able to use spreadsheets to model aspects of their lives and it could be argued that, outside of the Internet, it's the single most important tool available to us on a computer. It gains this power by providing a simple and intuitive set of tools for shaping just one material: a grid of numbers. If we want to work with more than that, however, we have to code.

A fundamental disconnect

Coding requires us to break our systems down into actions that the computer understands, which represents a fundamental disconnect in intent. Most programs are not trying to specify how things are distributed across cores or how objects should be laid out in memory. We are not trying to model how a computer does something.3 Instead, we are modeling human interaction, the weather, or spacecraft. From that angle, it's like trying to paint using a welder's torch. We are employing a set of tools designed to model how computers work, but we're representing systems that are nothing like them.4

Even in the case where we are talking specifically about how machines should behave, our tools aren't really designed with the notion of modeling in mind. Our editors and debuggers, for example, make it difficult to pick out pieces at different depths of abstraction. Instead, we have to look at the system laid out in its entirety and try to make sense of where all the screws came from. Most mainstream languages also make exploratory creation difficult. Exploring a system as we're building it gives us a greater intuition for both what we have and what we need. This is why languages that were designed with exploration in mind (LISP, Smalltalk, etc) seem magical and have cult followings. But even these suffer from forcing us to model every material with a single tool. Despite having different tools for various physical materials, in programming we try to build nearly everything with just one: the general purpose programming language.

On the surface, it seems desirable to have "one tool to rule them all," but the reality is that we end up trying to hammer metal with a chef's knife.5 Excel, by contrast, constrains us to the single material that it was intentionally designed to work with. Through that constraint we gain a tool with a very intuitive and powerful interface for working with grids. The problem of course is that Excel is terrible for doing anything else, but that doesn't mean we should try to generalize a chef's knife into a hammer. Instead, we should use the right tools for the job and look for a glue that allows us to bring different materials together.6

Programming as it exists now forces us to model, but it does so in an unnatural way. And while teaching ourselves how to program will help us learn how to break systems down, it does so at the risk of focusing on the wrong things.7We don't want a generation of people forced to care about Unicode and UI toolkits. We want a generation of writers, biologists, and accountants that can leverage computers.

How we teach children

We are natural-born modelers and we learn by creating representations that we validate against the world. Our models often start out too simplistic or even obviously wrong, but that's perfectly acceptable (and arguably necessary8), as we can continue to update them as we go. Any parent could give you examples of how this plays out in their children, though they may not have fully internalized that this is what's happening. A great example is that infants initially have a model of existence that relies on seeing objects. This is why not being able to see their parents is so distressing - it means that they no longer exist.9 The notion of object permanence is something that children only fully develop after a couple years of honing their model for how physical objects behave.

So if we do this naturally, what do we have to teach children? The magic of instinct is that we don't have to be aware of how it actually happens. We understand the world through models, but that doesn't mean we know how we create them in the first place. As such, we have to teach children how modeling happens,10 which we can break down into four distinct processes:

Specification: How to break down parts until you get to ideas and actions you understand.

Validation: How to test the model against the real world or against the expectations inside our heads.

Debugging: How to break down bugs in a model. A very important lesson is that an invalid model is not failure, it just shows that some part of the system behaves differently than what we modeled.

Exploration: How to then play with the model to better understand possible outcomes and to see how it could be used to predict or automate some system.

Focusing on these four areas captures the basic process by which we create, hone, and use models and it allows children to become active participants in the process by which they learn. Perhaps even more importantly, focusing on modeling pushes education towards the idea that pedagogy is really guiding children to deliberately create and explore the world around them.11

How we should teach adults

Realistically, we should be teaching ourselves the same things, but unfortunately adult education rarely allows for undirected exploration (we're just trying to get something done). Instead, we could frame modeling in terms of how we might use models in context. For example, if you're an accountant that goes through the same process every day to create a report, you could break it down to see how you might automate portions of it. What are the fundamental actions necessary to create that report? Are there tools that can do those actions for you?

If we assume that at some point better tools for modeling come into existence12, then being able to model some system or process may be all you need to automate it. Once that is the case, a targeted exploration of how you go about modeling specific domains has obvious value as it frees us up to do other tasks. An extreme example of this might be modeling your entire business, from the interactions with customers to fulfillment. At that point you could automate large portions of it and focus on how to grow the business, which itself likely involves exploratory models.

"The computer revolution hasn't happened yet"

Alan Kay did a talk at OOPSLA in 1997 titled "The computer revolution hasn't happened yet," in which he argued that we haven't realized the potential that computers can provide for us. Eighteen years later, I still agree with him - it hasn't happened yet. And teaching people how to loop over a list won't make it happen either. To realize the potential of computers, we have to focus on the fundamental skills that allow us to harness external computation. We have to create a new generation of tools that allow us to express our models without switching professions and a new generation of modelers who wield them.

To put it simply, the next great advance in human ability comes from being able to externalize the mental models we spend our entire lives creating.

That is the new literacy. And it's the revolution we've all been waiting for.

~ January 26, 2015

Mozilla to open first-world front in Firefox OS war

1 March 2015 - 8:00pm

A partnership with Verizon and other carriers is aimed at bringing the browser-based operating system to wealthy countries. But don't expect ordinary slab-of-glass phones.

Firefox OS is Mozilla's browser-based operating system. Mozilla

BARCELONA -- Mozilla announced partnerships with Verizon Wireless and other carriers to bring phones running its Firefox OS to wealthy countries where the browser-based mobile operating system today is all but unknown.

The partnerships will mean Firefox OS phones in the United States, but Verizon isn't the only partner. Others announced here at the Mobile World Conference show are Japanese carrier KDDI, South Korea's LG U+ and Spain's Telefonica, and the first phones from the deals are expected in 2016.

The partnerships are notable given that Firefox OS so far has largely competed in developing countries where smartphone penetration is relatively low and where Firefox OS's low-end hardware needs can mean more affordable products. When Mozilla first announced Firefox OS two years ago, it listed Sprint as a partner and planned to reach the United States, but it backed off that plan after a few months.

Spreading into wealthy countries could help encourage more programmers to support Firefox OS. And that, in turn, could help Mozilla advance its Firefox OS mission: to break down some of the barriers that keep customers locked into the iOS or Android technologies. Success would mean Google and Apple app stores would cease being a gateway to software and content, that apps purchased once wouldn't have to be purchased again if customers changed smartphone OSes, and that programmers could write an app just once with Web technologies that span not just iOS, Android, and Firefox OS, but also Windows Phone, BlackBerry OS, Tizen, Ubuntu and any other mobile operating system that arrives tomorrow.

Firefox OS has gradually spread to higher-end smartphones with the mainstream slab-of-glass touchscreen design, but many of the Firefox phones stemming from the new partnerships will embrace earlier phone designs that flip or slide open or that have hardware keyboards, said Mozilla Chief Technology Officer Andreas Gal.

"The operators see customer demand for these form factors. With Firefox OS we have the ability to actually serve that market," Gal said. "You'll see us broadening the categories we're bringing Firefox OS to."

The phones still won't take on Android and iOS flagship devices head-on. They'll be geared chiefly for entry-level customers upgrading from feature phones, Gal said. But those customers still want apps, fast mobile networks, and other modern features, he said.

"We see less and less competition in the entry-level segment with Android trending higher and higher in specs and Nokia Asha kind of disappearing," Gal said.

Small share

Mozilla needs every ally it can muster to take on the giants of the smartphone OS market, Apple's iOS and Google's Android. The former is the foundation for an immensely profitable business, and the latter powers most of the smartphones shipped today.

Going by market share, Firefox OS hasn't been a success, said Annette Zimmermann, research director for Gartner's consumer markets and technology group. "In a 1.2 billion smartphone unit market in 2014, they only shipped a bit over 2 million units," she said, and only a limited number of handset makers -- chiefly ZTE, Huawei, and TCL's Alcatel brand -- have embraced the OS, though that's changing with newer, bigger, higher-end models.

But what about progress with Mozilla's broader ambitions, to infuse the mobile technology with the openness that prevails on the Web? "I don't see any," Zimmermann said.

Mozilla CTO Andreas Gal Mozilla

Gal is patient, though.

"There are hundreds of millions of phones being sold every year -- more than billion. It takes time to grow in that market," Gal said.

Firefox OS phones are now available through 15 carriers in 30 countries, Gal said, and the Orange deal will increase that by another 13. Mozilla said that each month, about 3 million people visit its app store, the Firefox Marketplace, and download millions of apps.

And Mozilla's initial low-end thrust -- including a major new partnership with Orange to bring Firefox OS to 13 countries in the Middle East and Africa announced here -- could be helpful in the longer run. Analyst firm GfK believes smartphone growth rates will slow in 2015 "due to developed markets reaching saturation point," said analyst Kevin Walsh.

As a result, growth will shift to developing economies that buy cheaper phones. "We forecast emerging regions [will] drive growth in 2015 as smartphones further penetrate lower price points," he said, chiefly those costing less than $100.

Developer recruitment troubles

A strong point of Firefox OS is that, since it's a browser-based operating system, it can in principle just load a Web site or Web-based app. Even with iOS and Android apps a top developer priority, it's important to have a presence on the Web, too.

In practice, though, making sure Web apps are tailored for the small screen and tested with Firefox OS is another matter. Take the view of Erez Pilosof, chief executive of Hop, a startup trying to remake the world of email with a text messaging-style interface. It's currently developing a version of Hop for browsers on people's PCs based on its users' requests, Pilosof said. "We'll consider porting the Web version to Firefox OS, but I must say we have lots of users and never received a request for Firefox OS," he said.

Another pessimist is Rob McCarthy, technical advisor at Mobiquity, which develops mobile apps for a wide range of business clients.

"The only place we see Firefox going as a mobile OS is down-market, to people who can tolerate limited apps, less than ideal performance and low-end device quality," he said. "The OS itself does not do enough to enable it to be cost- or feature-competitive to Android in any mature market. Without that competitiveness, it's hard to see the value a developer can get out of Firefox OS in selling apps."

Even Mozilla's Firefox OS partners say the app situation needs work. "We also want to see them develop the ecosystem," said Jean-Marc Polga, Orange's device program manager.

Web apps need better performance before they can run apps like Looksery, which analyzes faces in video to add special effects to people's appearance, said Looksery CEO Victor Shaburov. "This will not run as HTML5 now," he said. "Unfortunately we will not be able to support Firefox OS." Mozilla is working to cater to developers like him and game authors, though, with a JavaScript-speeding technology called asm.js.

Undercutting Android, influencing iOS

Gal, though, looks at more criteria for success than just apps. He also considers influence on iOS and Android.

Those operating systems, he said, have followed Mozilla's lead in advancing mobile Web technologies. "Today Android and iOS have more capabilities -- they have accepted APIs [application programming interfaces] that we proposed," Gal said. "The goal with Firefox OS is not just Firefox OS, but but make sure other OSes support the same APIs."

And even though Google's Android One program is bringing cheaper Android phones to developing countries, Firefox OS can undercut it.

"We heard back from vendors in India in particular that for them Firefox OS worked out better in sales numbers than Android One," Gal said, with the competition costing three or four times as much.

Firefox OS is maturing, too, and Gal thinks that will change how it looks and works.

"We had in the beginning to catch up to things native ecosystems could do three or four years ago," like Bluetooth or NFC radio communications. "The next step is less familiar territory -- to use the unique advantages of the Web and expose them more to the user," he said.

Specifically, that means making it easier to use software. With browsers today, you simply go to a Web page and it loads. There's no app store searching, downloading and installing.

With the Web, "You don't have to install something, you just experience it. When you go Amazon.com you don't download something. We think that's a more powerful experience than on iOS or Android," and he hopes Firefox OS will apply some pressure toward openness because of it.

12 fascinating optical illusions show how color can trick the eye

1 March 2015 - 8:00pm
By Ana Swanson February 27

The design director of Roman Originals, the company that manufactured the dress that has caused a worldwide debate on its color, has confirmed the true hue of the frock - royal blue and black. (AP)

The Internet erupted in an energetic debate yesterday about whether an ugly dress was blue and black or white and gold, with celebrities from Anna Kendrick (white) to Taylor Swift (black) weighing in. (For the record, I’m with Taylor – never a bad camp to be in.)

It sounds inane, but the dress question was actually tricky: Some declared themselves firmly in the blue and black camp, only to have the dress appear white and gold when they looked back a few hours later.

Wired had the best explanation of the science behind the dress’ shifting colors. When your brain tries to figure out what color something is, it essentially subtracts the lighting and background colors around it, or as the neuroscientist interviewed by Wired says, tries to “discount the chromatic bias of the daylight axis.” This is why you can identify an apple as red whether you see it at noon or at dusk.

The dress is on some kind of perceptual boundary, with a pretty even mix of blue, red and green (frankly, it’s just a terrible, washed out photo). So for those who see it as white, your eyes may be subtracting the wrong background and lighting.

Changing a color’s appearance by changing the background or lighting is one of the most common techniques in optical illusions. As the examples below show, colors can change dramatically against different backgrounds. (If you’ve ever held a sock up to something black to see whether it was black or navy, you understand the concept.)

For example, in this classic shadow illusion by Edward H. Adelson, A and B are the exact same shade of grey:

Here's a minimalist illustration by Wikipedia user Dodek. The grey bar across the center is actually one constant color:


In this image from BrainDen, the surface colors of A and B are the same. To test it out, just use your finger to cover the middle of the drawing, where the two squares meet.

In this illusion by Barton L. Anderson and Jonathan Winawer, the black and white chess pieces are the same color:


If you want a dog of a different color, just set it against a different background (via BrainDen):

There are actually only two colors in this image -- red and green (sorry, color blind people). Also via BrainDen.

The blue and yellow border around this image by Jochen Burghardt creates the illusion that it is pale yellow, instead of white:

Contrasting colors can even give you the illusion of motion, as in this trippy graphic by Paul Nasca:


The same principle is at work in this motion illusion by Cmglee, which is based on Akiyoshi Kitaoka's "Rotating Snakes." As you stare at the image, the circles will appear to turn.


Cmglee

If you stare at the center of this illusion by Jeremy Hinton, you will eventually see a revolving green circle. When the lilac disappears, the adaptation of rods and cones in the retina leaves a green afterimage.

In Pinna's illusory intertwining effect, shown here in an illustration by Jochen Burghardt, colors give the illusion that circles are intertwining (they are actually concentric).

But probably the best illusion on the subject of the dress is by Randall Munroe of Xkcd, who immortalized the debate in an optical illusion cartoon form.

Ana Swanson writes for Know More and Wonkblog.

Forget the ‘To-Do’ List, You Need a ‘Stop Doing’ List

1 March 2015 - 8:00pm
Forget the 'To-Do' List, You Need a ‘Stop Doing’ List

Your browser, Internet Explorer 8 or below, is out of date. It has known security flaws and may not display all features of this and other websites.

Learn how to update your browser

TAP

U.S. Edition

San Francisco's Drug Geography

1 March 2015 - 8:00pm

I recently grabbed all crime data captured by the SFPD Crime Incident Reporting system, which is available through SF open data. It has ~1.7 million records from the past 12 years with a temporal and spatial stamp on each one. I've been interested in digging into some GIS data, so this is awesome!

SF is broken up into 10 police districts. Each record in the data is associated with a district as well as a specific crime category. I show the counts across the general crime categories below and used iPython notebook (linked here), Seaborn, and pandas for the work. Welcome others to view or pull it.

There's a lot to chew on, but I decided to drill down on the DRUG/NARCOTIC category. I grouped reported incidents based upon drug type (see notebook for details): the ordering in the below chart is HEROIN (blue, on the bottom), HALLUCINOGENIC, METH, MARIJUANA, COCAINE, CRACK (red, on top). I split the data into 30 day windows ranging from Jan, 2003 to Feb, 2015 (below). The top shows absolute incident counts per window and the bottom normalizes them to show a percentage.

I looked at the drug distribution over time for each district. They look different. For example, TENDERLOIN (top) has been dominated by CRACK-related incidents (though this has changed in recent years). PARK (which is basically Haight-Ashbury) is mostly MARIJUANA-related incidents.

To examine that idea, I counted up incidents in each drug category for each district. Then, I just normalized the data so each district is a vector that sums to one. Then, I cluster this (shown below). Each column (district) sums to one, so we can compare the normalized "drug profile" of each district. For example, TARAVAL, PARK, and RICHMOND have mostly MARIJUANA-related incidents.

The three clusters that fall out seem to show that drug similarity seems to mirror that actual geography of the city from East to West (SFPD district map shown below). CRACK has historically (remember this data goes back 12 years!) dominated in NORTHERN, MISSION, and TENDERLON. BAYVIEW, SOUTHERN, CENTRAL, and INGLESIDE have been a mix of CRACK, METH, and MARIJUANA.

Because this data is timestamped, we can look at the temporal trends as well. The most striking trend I saw was the drop-off in CRACK-related incidents. Below is a timeseries of crack-related incidents with three equally long windows: the mean incident count in the red window is ~5-fold greater than the green. It looks like CRACK is becoming a smaller fraction of the drug landscape.

One way to examine this is to look at the raw GIS data associated with each report. I used python's Basemap library to plot the geo-tagged CRACK-related incidents in each interval on a map of SF. Based on the GIS data, it CRACK's spatial footprint is getting small as the number of incidents drops.

If you back to the data at top, the total number of drug-related incidents has been dropping. The mix is becoming more equally distributed between CRACK, MARIJUANA, and METH. But, there's a lot more to look at with this data. I invite folks to pull the notebook and explore for themselves!

Timesheet.js

1 March 2015 - 8:00am

Visualize your data and events with sexy HTML5 and CSS3. Create simple time sheets with sneaky JavaScript. Style them with CSS and have mobile fun as well …

Just include Timesheet.js and configure your data. No external dependencies, no jQuery needed and of course no Angular.JS! Just a few lines JavaScript to generate a beautiful HTML5 layout and some really delicious CSS to be customized by mighty you.

<script src="/javascripts/timesheet.js" type="text/javascript" />

Create a simple time sheet based on a JS array of events:

new Timesheet('timesheet-default', 2002, 2013, [ ['2002', '09/2002', 'A freaking awesome time', 'lorem'], ['06/2002', '09/2003', 'Some great memories', 'ipsum'], ['2003', 'Had very bad luck'], ['10/2003', '2006', 'At least had fun', 'dolor'], ['02/2005', '05/2006', 'Enjoyed those times as well', 'ipsum'], ['07/2005', '09/2005', 'Bad luck again', 'default'], ['10/2005', '2008', 'For a long time nothing happened', 'dolor'], ['01/2008', '05/2009', 'LOST Season #4', 'lorem'], ['01/2009', '05/2009', 'LOST Season #4', 'lorem'], ['02/2010', '05/2010', 'LOST Season #5', 'lorem'], ['09/2008', '06/2010', 'FRINGE #1 & #2', 'ipsum'] ]);

It's that simple to use Timesheet.js. So, have a nice day, thank you for smoking and maybe try using Timesheet.js with custom styles …

dark | light

Super Hexagon Bot

1 March 2015 - 8:00am

The only way to beat this game is to let a robot do it.

Alright, alright it’s not the only way, people managed to finish this game without cheating.

Project idea

Anyway, that’s not the point. The point is that a bot for this game makes a really nice image processing project to start learning OpenCV: simple shapes but lots of human disturbing effects, fast-paced game meaning real-time is required, very simple controls: rotate CW or CCW.

The idea came to me after struggling to beat the 3rd level out of 6 of Super Hexagon. At this time I had already to many projects going on but I saved it for later. 3 months later, (still trying to beat level 4…) I proposed the idea for a software project at the end of the 2nd year of engineering school and it got accepted, yeah! I teamed up with my friend JP and I’ll finally get to beat the game (hopefully!).

Grabbing the video, real-time

We tried at first to record the screen with video capture software like Fraps or VLC and create a video stream that could be grabbed by OpenCV, but the received frames were lagging up to 2 seconds behind.

The solution we used was API Hooking with DLL Injection. It allows one to make the program jump to your own code (residing in a carefully crafted DLL) instead of executing a particular function from a DLL. This tutorial helped me to understand how it works, and the process to make it work. In short, this is how it works: The injection of a DLL calls an “on load” function that replaces the first 6 bytes of the hooked function by a JMP instruction to your code, followed by a return. Every time the hooked function is called, your code will run, then the return instruction will be called, skipping the rest of the original function. You can remove the hook by replacing the JMP instruction by the original instruction.

Before hooking theFunction() theFunction() hooked to myFuntion_hook()

Using OllyDbg, I found that the game called glutSwapBuffers() from glut32.dll. This function is used after all the graphics content is drawn to the back buffer and just before the front and back buffers are swapped. Note that now my code is executed by the game itself, in its own context. I can simply read the buffer and convert it to a cv::Mat image.

Of course, because we replaced the function with our own, we have to actually swap the buffers by explicitly calling the original glutSwapBuffer() function. I did this by undoing the hook, calling the original function and hooking it again.

Image processing

The image processing library we use is OpenCV. None of us ever used it before, but the community and tutorials are numerous, so it’s quite easy to get started with it.

This game is full of color changes, rotations, perspective deformation and other effects aiming at destabilizing the player. Before any image recognition occurs, we have to preprocess each frame in order to be able to find the walls and the ship.

Preprocessing

Starting from the original frame, we mask the black and white text with the color in the center. Then the RGB channels are merged into one by going to a grayscale palette. Before binarizing, we normalize the image. Normalizing extends the range of color: the darkest gray is transformed into full black, the lightest gray becomes full white and the grays in between are scaled. The binarization is a simple threshold. Everything over the threshold gets white, everything under it is black.

After these steps, we end up with the walls, the ship and the central shape in white, on a black background.

Ship

Now that the frame is cleaned and standardized, we can detect the ship, the small triangle rotating close to the center.

The ship is detected by resemblance

We crop the image to keep only the center part. Then we use a high-pass filter and the function findContours() to detect all the polygons in the image. We do the same for the ship’s model image and find the most resembling polygon with matchShapes().

Once detected, the ship’s center is computed as well as its angular position. We then mask the ship with a black disk, it is not needed for the next steps.

Central shape

Usually, the arena of this game is constituted of 6 sectors (hexagon), but sometimes, sectors are removed and the central shape changes accordingly into a pentagon or a square. We need to detect this.

We use the list of contours from the ship detection and remove the polygons with an area too large or too small. We also remove polygons that are not centered (cropped walls). The central shape is the polygon with the smallest area. The number of edges from 4 to 6 tells us the shape, but we can extract more information about the arena.

The arena is constantly rotating and we need to detect the angular position (or the angle) of each sector’s bisector. We do this by computing the normal to each edge that crosses the center of the frame. With some clever filtering and averaging with the 6 edges, we get a good estimation of how much the arena rotated, with very little noise.

Detecting the walls

The walls are white polygons on a black background. We could have detected them all, but the IA I coded only needs 3 distances per sector:

  1. d1: the distance from the center to the inside edge of the central shape.
  2. d2: the distance from the center to the outside edge of the central shape.
  3. d3: the distance from the center to the first wall.

d1 and d2 will be used to get rid of the scaling/zooming effect and d3 is the measure of how good this particular sector is. The further the first wall, the better.

I measure these 3 distances by “casting” a ray along the bisector of the sector. d1, d2 and d3 are the distances at which the color of the pixel along the bisector goes from black to white, white to black and again black to white. d3 is capped by a circle to avoid advantaging directions due to the rectangular shape of the frame.

Wall detection

This is the result for different patterns:

IA strategies

The first IA I coded managed to stay alive for the first 40s of the level 1. It was a very simple and temporary IA, although the final version is just an amelioration of it.

For simple patterns, the best choice is always to go toward the sector with the greatest distance d3. As the walls get closer, the way out is indeed these sectors:

The IA then drives the ship to the best sector by simulating keys presses (left or right), rotating in the shortest direction.

Problems

As you can imagine, the 40-second barrier is due to more complex patterns appearing around this time.

Complex pattern 1: the hook

Using only d3, the correct way out is found: the top right sector. The shortest path is to rotate clockwise but this way is obstructed by a wall. With d1 and d2, we can detect that there is a wall: (d2-d1) much greater than d1. By testing every sector on the way, the IA can choose to rotate in the other direction if there is a wall.

Unfortunately, this is not enough:

Complex pattern 2

In this pattern, the way out is detected, and both directions are free from walls. Or are they?… The sector that IS the way out is detected as a wall itself! This means that both CW and CCW rotation are invalid. The IA will wait until the wall disappears and then move, but it will be too late…

New version

The solution I came up with is to look for the “best” sector once CW and once CCW. The wall detection is dropped and replaced by an accessibility condition. A sector is accessible if there is enough space (d3-d2 large enough) to let the ship pass to this sector from the previous one: d3(i-1)-d2(i) and d3(i)- d2(i-1) must be large enough for sector i to be consider accessible from the sector i-1.

I must tell you that the walls are not lethal by themselves. You lose the game is your ship gets crushed by a wall. But you can hit the side of an obstacle with your ship without any problem.

This IA works well for all the patterns, and actually beat the game (the 6 levels!). It manages to beat levels 1, 2, 3 and 4 almost everytime. Levels 5 and 6 requires a couple of trials before a good run. You can see it performing on the 3rd level:

Like this:

Like Loading...

8cc: A Small C Compiler

1 March 2015 - 8:00am
README.md

8cc is a compiler for the C programming language. It's intended to support all C11 language features while keeping the code as small and simple as possible.

The compiler is able to compile itself. You can see its code both as an implementation of the C language and as an example of what this compiler is able to compile.

8cc's source code is carefully written to be as concise and easy-to-read as possible, so that the source code is eventually be a good study material to learn about various techniques used in compilers. You may find the lexer, the preprocessor and the parser are already useful to learn how C source code is processed at each stage.

It's not an optimizing compiler. Generated code is usually 2x or more slower than GCC's. I plan to implement a reasonable level of optimization in the future.

8cc supports x86-64 Linux only for now. I have no plan to make it portable until I fix all known miscompilations and implement an optimization pass. As of 2014, I'm using Ubuntu 14 as my development platform. It should work on other x86-64 Linux distributions though.

Note: Do not have high expectations on this compiler. If you try to compile a program other than the compiler itself, there's a good chance to see compile errors or miscompilations. This is basically a one-man project, and I have spent only a few months of my spare time so far.

rui314@gmail.com

Xfce 4.12 released

1 March 2015 - 8:00am

Xfce 4.12 is be the best release ever (yes, we like to party!)!

Source : Internet comments.

Today, after 2 years and 10 months of work, we are pleased to announce the release of the Xfce desktop 4.12, a new stable version that supersedes Xfce 4.10.

This long period can only be explained by how awesome Xfce 4.10 was. But as all things, it needed some refreshing - and for that we saw lots of new contributors providing valuable feedback, features and bugfixes. As always, Xfce follows its steady pace of evolution without revolution that seems to match our users' needs.

In this 4.12 cycle, we mainly focused on polishing our user experience on the desktop and window manager, and on updating some components to take advantage of newly available technologies.

The main highlights of this release are:

  • The window manager gained a new themable Alt+Tab dialog with optional windows preview and a list mode. Initial Client side decoration support was implemented, window tiling mode was improved providing support for corner-tiling, and a new zooming mode was added. A HiDPI Xfwm theme was also added.
  • The panel can now intelligently hide itself, supports Gtk3 plugins, and saw lots of its third-party plugins updated to take full advantage of the features added in 4.10.
  • The desktop has a new wallpaper settings dialog, per workspace wallpaper support, and better multi-monitor handling. It also supports displaying folder cover art and emblems on icons now.
  • Our session manager was updated to use logind and/or upower if available for hibernate/suspend support. For portability and to respect our users' choices, fallback modes were implemented relying on os-specific backends.
  • Support for multi-monitor use was improved in a new display settings dialog and a quick setup popup on monitor plugging.
  • The appearance dialog now showcases previews for icons and themes.
  • Xfsettingsd now supports libinput.
  • Power management was not forgotten: A new panel plugin was created, logind/upower support was added to handle battery/lid/brightness events, and locking via light-locker was implemented. The settings dialog was also revamped, and support for X11 screenblanking was added.
  • Our file manager, the beloved Thunar, saw an insane amount of improvements: tab support, tons of bug fixes, speed-ups, key shortcuts for custom actions, better naming of file copies and links, nice freespace bar in properties, tweaks for the renamer and other dialogs, improved keyboard navigation, fixes for the treeview pane, better wallpaper support, Gtk3 bookmarks support, multiple file properties... need we say more?
  • To prepare the future of Xfce with Gtk3, which no longer requires theme engines, we are stopping the development of our Gtk theme engine, and dropping our Gtk3 engine - theme makers, please update your themes to CSS if you want them to work on the next Xfce version.
  • Due to gstreamer1.0 having dropped the mixer-interface entirely, and xfce4-mixer and xfce4-volumed relying on this interface with gstreamer0.10, our mixer application and volume daemon cannot be ported to 1.0 and are consequently not maintained anymore.

Xfce wouldn't be what it is right now without all its goodies. In this area, we also saw a flurry of activity, most notably:

  • Xfburn gained BluRay Disc burning support.
  • Task manager UI was totally revamped, and got ported to Gtk3.
  • Parole's UI was totally redone, parts of it rewritten with many features added. Furthermore it was ported to Gtk3 and gstreamer1.0.
  • Mousepad was totally rewritten and got an initial port to Gtk3.
  • Imgur.com support was added to the screenshooter.
  • A new GNOME-Shell-like dashboard named xfdashboard is now available.
  • A new alternative menu for the panel named whiskermenu was added.
  • The GNOME2 hardware monitor plugin was ported to our panel.
  • Weather plugin got a totally new user interface with powerful customization options and provides tons of detailed information.
  • Eyes plugin uses 3D coordinates to calculate its eye position, so even more sometimes scary, sometimes funny eyes will spy on you!
  • Netload plugin works with the new udev net interface names and can be configured to show transfer rates in the panel.
  • Clipboard manager plugin optionally displays a QR code.
  • Cpufreq plugin now supports the intel pstate driver and can adapt better for different panel sizes and information displayed.
  • Nearly all plugins have been improved to give the same look and feel and to support the new deskbar panel mode.

An online tour of the changes in Xfce 4.12 can be viewed here:

http://xfce.org/about/tour

A detailed overview of the changes between Xfce 4.10 and Xfce 4.12 releases can be found on the following page:

http://xfce.org/download/changelogs

This release can be downloaded either as a set of individual packages or as a single fat tarball including all these individual versions:

http://archive.xfce.org/xfce/4.12

A warm thank you all the contributors, translators and packagers for your efforts in making this release possible. We would also like to thank our fantastic users and occasional contributors who submitted bug reports, helped us find issues and sometimes provided patches. We are currently reviewing all patches sent to us and will include many more fixes to Xfce in the next release. We would also like to thank the many people who donated money to our project via Bounty Source. This will help us meet and hack on Xfce in the future!

As always, we welcome everyone who would like to contribute to the development of Xfce! You can either test Xfce and report bugs, you can help us with translations and documentation, with usability and user experience by packaging Xfce into your distribution, and by submitting patches or entirely new features! You can get in touch with us on the Freenode IRC channel #xfce-dev and our mailing list.

Best regards,
The Xfce development team

Most Down-Voted Stack Overflow Questions

1 March 2015 - 8:00am
-- Most Down-Voted Questions -- The top 20 questions with the most down-votes (ignores up-votes) select top 20 count(v.postid) as 'Vote count', v.postid AS [Post Link],p.body from votes v inner join posts p on p.id=v.postid where PostTypeId = 1 and v.VoteTypeId=3 group by v.postid,p.body order by 'Vote count' desc

created jun 3 11

jon.doe5752

Enter Parameters

Run Query Cancel Options: Text-only results Include execution plan

To avoid spam queries, all anonymous users must solve a captcha

Whoops! Looks like you didn't get the captcha quite right, please try again.

I'm a Human Being!

Hold tight while we fetch your results

:records returned in :time ms:cached

For Asian Americans, a changing landscape on college admissions

1 March 2015 - 8:00am

In a windowless classroom at an Arcadia tutoring center, parents crammed into child-sized desks and dug through their pockets and purses for pens as Ann Lee launches a PowerPoint presentation.

Her primer on college admissions begins with the basics: application deadlines, the relative virtues of the SAT versus the ACT and how many Advanced Placement tests to take.

Then she eases into a potentially incendiary topic — one that many counselors like her have learned they cannot avoid.

“Let's talk about Asians,” she says.

Lee's next slide shows three columns of numbers from a Princeton University study that tried to measure how race and ethnicity affect admissions by using SAT scores as a benchmark. It uses the term “bonus” to describe how many extra SAT points an applicant's race is worth. She points to the first column.

African Americans received a “bonus” of 230 points, Lee says.

She points to the second column.

“Hispanics received a bonus of 185 points.”

The last column draws gasps.

Asian Americans, Lee says, are penalized by 50 points — in other words, they had to do that much better to win admission.

“Do Asians need higher test scores? Is it harder for Asians to get into college? The answer is yes,” Lee says.

Zenme keyi,” one mother hisses in Chinese. How can this be possible?

College admission season ignites deep anxieties for Asian American families, who spend more than any other demographic on education. At elite universities across the U.S., Asian Americans form a larger share of the student body than they do of the population as a whole. And increasingly they have turned against affirmative action policies that could alter those ratios, and accuse admissions committees of discriminating against Asian American applicants.

That perspective has pitted them against advocates for diversity: More college berths for Asian American students mean fewer for black and Latino students, who are statistically underrepresented at top universities.

But in the San Gabriel Valley's hyper-competitive ethnic Asian communities, arguments for diversity can sometimes fall on deaf ears. For immigrant parents raised in Asia's all-or-nothing test cultures, a good education is not just a measure of success — it's a matter of survival. They see academic achievement as a moral virtue, and families organize their lives around their child's education, moving to the best school districts and paying for tutoring and tennis lessons. An acceptance letter from a prestigious college is often the only acceptable return on an investment that stretches over decades.

Lee is the co-founder of HS2 Academy, a college prep business that assumes that racial bias is a fact of college admissions and counsels students accordingly. At 10 centers across the state, the academy's counselors teach countermeasures to Asian American applicants. The goal, Lee says, is to help prospective college students avoid coming off like another “cookie-cutter Asian.”

“Everyone is in orchestra and plays piano,” Lee says. “Everyone plays tennis. Everyone wants to be a doctor, and write about immigrating to America. You can't get in with these cliche applications.”

::

Like a lot of students at Arcadia High School, Yue Liang plans to apply to University of California campuses and major in engineering — or if her mother wins that argument, pre-med. She excels at math, takes multiple AP courses and volunteers, as does nearly everyone she knows.

Being of Asian descent, the junior says, is “a disadvantage.” The problem, she says, is in the numbers.

Asian families flock to the San Gabriel Valley's school districts because they have some of the highest Academic Performance Index scores in the state. But with hundreds of top-performing students at each high school, focusing on a small set of elite institutions, it's easy to get lost in the crowd.

Of the school's 4,000 students, nearly 3,000 are of Asian descent, and like Yue are willing to do whatever it takes to gain entrance to a prestigious university. They will study until they can't remember how to have fun and stuff their schedules with extracurriculars. But there's an important part of their college applications that they can't improve as easily as an SAT score: their ethnicity.

In the San Gabriel Valley, where aspirationally named tutoring centers such as Little Harvard and Ivy League cluster within walking distance of high schools, many of them priced more cheaply than a baby-sitter, it didn't take long for some centers to respond to students' and parents' fears of being edged out of a top school because of some intangible missing quality.

Helping Asian American students, many of whom lead similar lives, requires the embrace of some stereotypes, says Crystal Zell, HS2's assistant director of counseling. They are good at math and bad at writing and aspire to be doctors, engineers or bankers, according to the cliches. She works with her students to identify what's unique about them — and most of the time, that's not their career ambitions or their ethnicity.

“Everyone comes in wanting the same thing,” Zell said. “But that's because they don't know about anything else.”

If a student wants to be an engineer, she makes sure to show other options. She sends affluent students to volunteer in poor neighborhoods. Branch out from tennis, or chess club, or taekwondo, she tells them. Learn a language other than Chinese. Avoid writing your essay about your parents' journey to America.

Instead of just handing students a violin or a piano and saying pick one, Zell says, HS2 offers them a buffet of interests and hobbies, encouraging students to pick something that excites them.

Lawrence Leonn, 16, is grateful for the help. He doesn't think race or ethnicity should matter, but he believes it will.

“I don't want to be racist or anything,” Lawrence said. “Everyone works hard and struggles. But there's this feeling that it's going to be harder for us.”

::

Complaints about bias in college admissions have persisted since at least the 1920s, when a Harvard University president tried to cap the number of Jewish students. In November, a group called Students for Fair Admissions filed a suit against Harvard University for admissions policies that allegedly discriminate against Asian Americans. The group cited the 2004 Princeton study and other sources that offer statistics about Asian Americans' test performance.

At the University of Texas at Austin, an affirmative action policy that allows admissions committees to consider the race of prospective applicants has been argued all the way to the Supreme Court. (The policies were upheld by a lower court, but that court's decision was voided by the Supreme Court. Another court upheld the policies and another appeal is pending.)

Those who defend “holistic” admissions policies insist that considering a broader range of variables ensures that all applicants are judged fairly. And the Princeton study Lee refers to has been widely criticized by academics who argue that it relies too heavily on grades and test scores to draw conclusions about racial bias and that the data the study uses are too old to be relevant.

Still, anxiety over racial admissions rates is peaking as cash-crunched public universities increasingly favor high-paying out-of-state and foreign students at the expense of local applicants of every ethnicity. A 2014 bill that would have asked voters to consider restoring race as a factor in admissions to public California colleges and universities sparked multiple public protests and scathing editorials in Chinese newspapers. The bill, Senate Constitutional Amendment 5, was shelved last year.

Lee says that she usually tries to at least mention arguments in favor of diversity at her free college seminars. She mentions how the black student population at UCLA has declined precipitously and how student bodies at elite universities probably shouldn't be 100% of Asian descent. When she looks to see the response, she sees mostly slowly shaking heads.

“It's really hard for me to explain diversity to parents whose only goal is getting their son into Harvard,” Lee says.

That same ethic causes parents and students to agonize over which box, if any, to check on the race and nationality section of the application. One parent asked Zell whether it would help to legally change the family name to something more Western-sounding.

Last year, a rumor that Harvard University would stop accepting any more Asian American students from San Marino High School spread like a trending hashtag.

Mollie Beckler, a counselor at San Marino High School, says that Harvard never imposed such a rule. School counselors are continually trying to dispel myths like these, she says, if only in hopes of slightly lowering the huge stress students shoulder because of their intense focus on elite schools.

“The feeling of failure they get from trying to reach such high standards,” she said, “is very concerning to us in the counseling world.”

Only a few of the San Gabriel Valley's tutoring centers confront the ethnic admissions issue head-on.

Jamie Aviles, a counselor at the ACI Institute, doesn't teach ways to overcome perceived racial bias, she says. But she and many other counselors do agree on at least one thing.

As Aviles puts it: “It sucks to be a kid in the San Gabriel Valley.”

frank.shyong@latimes.com

ALSO:

For a dad stung by stereotypes, 'Fresh Off the Boat' is point of pride

UC's enrollment guarantee gives students an education to fall back on

China complains SAT may impose American values on its best students

Copyright © 2015, Los Angeles Times

Microwave Oven Diagnostics with Indian Snack Food

28 February 2015 - 8:00pm

Microwave ovens are curious beasts. A super convenient method of warming up certain foods, for boiling a cup of water, melting a little butter, or reheating frozen leftovers. But all too often, those frozen leftovers end up scorching in places and rock-hard frozen in others. Is this just random? Is it really the case that microwaves cook the food from the inside out or left to right or back to front? Well, no, but the way that microwaves work can be mighty counter-intuitive. Our own microwave oven is definitely one of those that likes to produce scalding yet frozen output. That isn’t necessarily such a big deal if you have patience to reposition a dish several dozen times in the course of a five minute warm up. But we recently (and quite unintentionally) came across a situation– while cooking, of all things –where the radiation pattern became clear as day.
As we have written about, we enjoy roasting papadums (a type of Indian cracker) on the stovetop. Appalams are a closely related cracker made with rice flour in addition to the usual lentil flour that can be cooked in the same ways, but just happen to be significantly more flammable.
So, while you can (with great care and a nearby fire extinguisher) roast appalams on the stovetop, we decided to try out the microwave method. We put several of the appalams on a plate. They start out as plasticky brittle wafers like you see above. And then, after 30 seconds in the microwave, here is what we saw:
Holy crap! As an area of the cracker cooks, it bubbles up in just a few seconds, leaving clear marks as to where there is microwave power and where there isn’t. For this particular microwave, Saturn-shaped objects will cook evenly. Obviously what is happening is that there are two hotspots in this microwave: one in the center, and one offset from center which traces out a circle thanks to the rotating plate in the bottom. We have access to four other microwave ovens. Are they all this bad?For each microwave, we spread out four appalams on a plate and cooked them for 30 seconds.
Microwave #2: This microwave cooked much more evenly, but is better suited for reheating donuts: it has a dead zone in the very center, a central ring that cooks well, and an outer dead ring with hotspots beyond that.
Microwave #3: This is a very large microwave–the kind that a turkey would fit in. It is extremely powerful, but strangely, the cooking is confined to a single central area that is much smaller than its rotating tray. This is the one you should use to heat your soup for lunch. Alternately, an appalam placed dead-center cooks beautifully in 30 seconds.
Microwave #4: Significantly underpowered, with a hotspot way off center and an outer ring of uneven distribution. Wondering why part of your lunch is steaming and part is still icy? Blame this microwave.
Microwave #5: This microwave has adequate power, but an absolutely baffling radiation pattern. Even though it has a rotating tray, there are two angular sections that are still plasticky raw. How can this happen? Our guess: the rotating tray is driven by a synchronous motor, while the magnetron is driven in pulses that are several seconds long. The resulting beat frequency shows up on your crackers. Consider this microwave a good candidate for firmware replacement.
Microwave #1 is clearly the worst of the bunch. One tiny warm spot in the center, and a narrow ring of mediocrity around it. Did you know that if you take apart microwave ovens, there is a really great ceramic magnet inside of the magnetron? And when we’re shopping for our next microwave, where can we go with our stack of appalams to try out prospective replacements?
One nice thing about this testing method: the cooked portion of the output makes for a great snack. Serve with chutney, pickles or other preserves. Print PDF

. Bookmark the

.

Live Sails.js Course

28 February 2015 - 8:00pm
Connect with Facebook Don't have a subscription? Sign Up

Learn with Mike McNeil, creator of Sails.js to develop web apps from zero to hero with Node.js, Socket.io, databases and Sails.js

Industry leaders teaching you

Learn with live streaming or with videos at your pace

Videos, tutorials and projects.

Q&A with answers from teachers, your peers and our team

Top carnivores increase their kill rates as a response to human-induced fear

28 February 2015 - 8:00pm
Abstract

The fear induced by predators on their prey is well known to cause behavioural adjustments by prey that can ripple through food webs. Little is known, however, about the analogous impacts of humans as perceived top predators on the foraging behaviour of carnivores. Here, we investigate the influence of human-induced fear on puma foraging behaviour using location and prey consumption data from 30 tagged individuals living along a gradient of human development. We observed strong behavioural responses by female pumas to human development, whereby their fidelity to kill sites and overall consumption time of prey declined with increasing housing density by 36 and 42%, respectively. Females responded to this decline in prey consumption time by increasing the number of deer they killed in high housing density areas by 36% over what they killed in areas with little residential development. The loss of food from declines in prey consumption time paired with increases in energetic costs associated with killing more prey may have consequences for puma populations, particularly with regard to reproductive success. In addition, greater carcass availability is likely to alter community dynamics by augmenting food resources for scavengers. In light of the extensive and growing impact of habitat modification, our study emphasizes that knowledge of the indirect effects of human activity on animal behaviour is a necessary component in understanding anthropogenic impacts on community dynamics and food web function.

1. Introduction

Anthropogenic disturbance can cause shifts in biotic community dynamics, generally through the loss of native species, introduction of novel species or artificially enhanced populations of native generalists [1]. These changes are characterized most often by quantifying the population size or presence of particular species. However, behaviour-mediated interactions are predicted to have equal or greater impacts on animal populations than purely numerical mechanisms [24]. Animal behavioural responses to anthropogenic disturbances have the potential to be cryptic but powerful drivers of ecological change in modified habitats [5].

Large carnivores are widely recognized to be sensitive to human disturbances owing to slow life cycles, large space requirements, direct persecution by humans and avoidance of human-dominated areas, often resulting in their decline or extirpation. Reduced large carnivore density and occupancy in some developed areas has resulted in both mesopredator release [6,7] and overpopulation of primary consumers [8,9]. Yet, some large carnivores do persist in modified landscapes, but alter their behaviour to reduce interactions with humans [10,11]. Owing to the strong regulatory influence large carnivores can exert on their competitors and prey, changes in their behaviour are likely to contribute to whole community responses to anthropogenic disturbances [12].

Hunting and foraging are costly behaviours for carnivores, but are often assumed to be optimized so that individuals gain the most energy (or other limiting nutrients) for the least effort [13]. Animals that choose to expend more energy than what is perceived to be optimal may be responding to risks that increase the long-term pay-off of certain energy-expensive behaviours through decreased chance of non-starvation mortality [14]. Hunting in high-risk habitats can therefore create a risk-foraging trade-off in which animals sacrifice efficient foraging to compensate for increased vigilance and risk avoidance. Giving-up density studies support that an animal's perceived risk is inversely correlated with food intake, suggesting that time spent consuming a food item reflects the fear experienced by forager [15].

Top carnivores generally kill large-bodied prey species, which require a high initial energetic cost during the hunting stage [16], but provide high energy gain during consumption. However, because carnivores are constrained by gut capacity, solitary carnivores can only maximize their caloric yield by repeatedly returning to feed on a prey carcass. In developed habitats, carnivores can be particularly vulnerable to risk-foraging trade-offs because disturbance-induced carcass abandonment can result in food loss owing to scavenging [17] or decomposition [18]. Prey consumption time can therefore be limited by external forces that reduce carnivore access to a carcass. Anthropogenic disturbances can ultimately reduce the net caloric gain carnivores receive from consuming large prey [19] by displacing carnivores from kill sites and decreasing their prey consumption time at kills. If perceived risk increases with human disturbance, the magnitude of human impact should be a predictor of foraging efficiency and consumption time.

We examined puma (Puma concolor) behavioural changes associated with perceived risk at kill sites with increasing housing density levels and investigated the relationship between risk-avoidance behaviours and kill rates in disturbed areas. We hypothesized that disturbance would displace pumas more often in highly developed areas, reducing overall prey consumption time and increasing kill rates. In the long term, we anticipate that more frequent risk-avoidance behaviours will increase puma kill rate and subsequently alter interactions with prey, competitors and scavengers.

2. Material and methods

Our research was conducted in the Santa Cruz Mountains, which lie in the Central Coast region of California. We captured 30 pumas from 2008 to 2013 and fitted them with GPS/radio telemetry collars (IACUC no. WILMC1011 Model GPS Plus 1 or 2 D, Vectronics Aerospace, Berlin, Germany). Collars were programmed to record locations every 4 h, and location data were downloaded remotely via UHF once a month. We used a custom cluster generation algorithm integrated in the Geographical Information Systems program ArcGIS (v. 10; ESRI, 2010) using the programming languages R (v. 2.1.3.1; R Development Core Team, 2010) and Python (v. 2.6; Python Software Foundation, 2010) to identify groups of locations in which each location was within 100 m of the cluster centre and 6 days of another location in the cluster (for full details on the algorithm, see [10]). We field-investigated clusters in reverse chronological order from their time of formation using the most recently downloaded GPS data. Clusters were investigated within 30 days of their first recorded locations. At investigated clusters, we recorded whether a kill was present, and if so, the species, age and sex of the kill (if identifiable).

We constructed a mixed-effects binomial logistic regression model to predict deer kill sites from all generated clusters. We chose to only use deer kills because deer are the preferred prey in our study area. In addition, small prey cannot be predicted accurately from location data in our study area owing to high variability in puma behaviours at small kill sites. The variables used to fit the model were behavioural characteristics associated with clusters, including number of night locations (NIGHT), a binary variable indicating greater than 1 day duration (BINARY), the harmonic mean distance of locations from the cluster centre within the cluster (HMDIST), the proportion of locations occurring at night (P.NIGHT), site fidelity measured by the proportion of points occurring within the cluster over the cluster duration (P.ACTIVE) and the farthest distance travelled during a cluster period (DIST). Total duration of a cluster (DUR) was excluded owing to high correlation (r > 0.7) with variables already used in the model. We allowed for random slopes and intercepts for individual pumas when fitting the best model. We also constructed a truncated model without behavioural variables that we expected to correlate with housing density in order to allow inference on behavioural influences on kill rates. This model excluded P.NIGHT, P.ACTIVE and DIST. We compared the truncated model and best-fit model to assess if we could confidently use the truncated model. We constructed receiver operating characteristic curves for both full and truncated models and calculated the area under the curve (AUC) to ensure that both models were similar in their predictive abilities. The AUC for the full model (AUC = 0.818) and the truncated model (AUC = 0.820) were nearly identical, and both support good discriminative ability [20]. We assigned each generated cluster as a deer kill or not a deer kill by applying the truncated model to all generated clusters.

We first investigated puma behavioural responses at the population level at four levels of housing density within 150 m of predicted kill sites: no housing, rural (greater than 0.0 and up to 0.062 houses per hectare), exurban (greater than 0.062 and up to 1.236 houses per hectare) and suburban (greater than 1.236 and up to 9.884 houses ha−1; [21]). Owing to the discrete nature of housing count data, each housing class was rounded up to the nearest number of houses, resulting in housing classes within 150 m of a cluster to be defined as 0 houses for no housing, one house for rural, two to nine houses for exurban and greater than nine houses for suburban. We used the 150 m buffer because this is the scale of development found to most impact puma hunting in our study area [10]. We constrained the response variables to only include behaviours we expected to be associated with risk aversion, which were narrowed down to P.NIGHT, P.ACTIVE, DUR, DIST and a final measure of prey consumption time (P.C.TIME) which was calculated as P.ACTIVE × DUR. We added the prey consumption time measure because it best reflects the energetic gain an animal receives from a kill. We tested the differences in behaviours at all predicted kill sites in different housing density categories using an ANOVA test and examined pairwise comparisons with Tukey's HSD test for all behaviours found to vary significantly with housing density.

To determine kill rates, we calculated the total number of deer predicted to be killed by each puma from the output of the deer kill prediction model using all generated GPS clusters. We divided the predicted number of kills by the total time each puma was actively collecting GPS data to obtain annual deer kill rates. We investigated sex-specific relationships between kill rates and average values for P.NIGHT, P.ACTIVE, DIST, DUR and P.C.TIME for individual pumas using univariate linear regressions owing to high correlation values (r > 0.7) among variables.

In order to assess the impact of housing on individual pumas, we calculated housing density within each puma home range. Puma home ranges were obtained using a local convex hull (LOCOH) home range estimator, where the 95% isopleth represented the home range boundary [22,23]. All housing points in the Santa Cruz Mountains were manually digitized from high-resolution satellite imagery. We calculated puma home range housing density as the number of houses per km2. We tested for the relationship between individual puma kill rates and home range housing densities using univariate linear regression.

3. Results (a) Behavioural shifts

Of 703 field-investigated clusters, 208 were classified as deer kill sites. The other remaining clusters included 66 non-deer kills (e.g. raccoons and house cats) and 429 non-kills (often bed sites). Our best-fit binomial logistic regression model to predict deer kills included NIGHT, BINARY, HMDIST, P.NIGHT and P.ACTIVE. The truncated model included NIGHT, BINARY and HMDIST. Neither the random intercept nor a random slope was included in the best-fit full model or the best-fit truncated model. We used the truncated model to predict 1537 deer kills from 8523 generated clusters (figure 1).

Figure 1.

(a) Study area and predicted kill sites in relation to housing density. Box shows area (b) in which kill site examples (c,d) are shown. Kill site 1 (c) belongs to puma 13F, whose home range is in the top quartile of housing densities among female pumas. Kill site 2 (d) belongs to 28F, whose home range in the bottom quartile of housing densities among female pumas. Grey labels depict location times during the first day at the kill site and black labels depict location times during the second day. Note that at kill site 1, the puma has made a kill close to development but spends the majority of time away from the kill, whereas at kill site 2, which has no nearby development, the puma stays within the vicinity of the kill. (Online version in colour.)

At predicted kill sites, females had lower P.ACTIVE (F = 67.7, ), higher DIST (F = 16.0, p < 0.001) and shorter P.C.TIME (F = 44.2, ) as housing density increased (figure 2; example shown in figure 1). In suburban habitat, female P.ACTIVE was 36% lower, DIST was 31% higher and P.C.TIME was 42% lower than in no housing areas. Both males (F = 19.3, p < 0.001) and females (F = 144.4, ) were more nocturnal (higher P.NIGHT) with increasing housing density at kill sites. Males did not show any responses to housing density concerning time spent at kill sites. Identical analyses using only confirmed kills supported each of the reported trends for predicted kills.

Figure 2.

Behaviours that vary with housing density at predicted kill sites. Pairwise comparisons from Tukey's HSD tests reported in superscripts, where different letters represent a statistically significant difference. Error bars represent two standard errors from the mean. Sample sizes of housing classes at female kills are: no housing, 719; rural, 83; exurban, 186; suburban, 71. Sample sizes of housing classes at male kill sites are: no housing, 389; rural, 32; exurban, 42; suburban, 15. (Online version in colour.)

(b) Deer kill rates

Male average home range size was 163.0 ± 7.7 s.e. km2 with 15.6 ± 0.8 s.e. houses km−2. Female average home range size was 53.8 ± 2.1 s.e. km2 with 25.5 ± 1.3 s.e. houses km−2. Males had an average deer kill rate of 43.7 deer yr−1, whereas females killed on average 67.3 deer yr−1. Male deer kill rates were not correlated with any of our variables of interest (P.ACTIVE, P.NIGHT, DIST, DUR or P.C.TIME), nor with home range housing density (p = 0.9, r2 = 0.005; figure 3). Conversely, female deer kill rates showed a strong positive and linear correlation with home range housing density within its observed range (p = 0.0003, r2 = 0.745; figure 3). Females with home ranges in the top quartile of housing density killed 36% more deer per year (81.2) than females in the bottom quartile of housing density (59.7). Female kill rates were also negatively correlated with average fidelity to kill sites (P.ACTIVE; p = 0.05, r2 = 0.322).

Figure 3.

Kill rates of individual male and female pumas in response to housing density per hectare within their 95% LOCOH home range. Regression line and 95% CIs for female kill rates in relation to housing density are shown. Housing density coefficient β1 = 91.4. (Online version in colour.)

4. Discussion

Our estimate of average male kill rates (43.7 kills yr−1) stayed constant across housing densities and was comparable to previously reported values described by Knopff et al. (35 ungulates yr−1, [24]) and Anderson & Lindzey (47 kills yr−1, [25]). However, female kill rates increased positively, strongly and linearly with housing density. Although female kill rates in lower housing density areas (59.7 kills yr−1) were comparable to previously estimated mule deer kill rates for solitary adult females (52.5 kills yr−1, [25]) and females with kittens (62.4 kills yr−1, [26]; 68.1 kills yr−1, [25]; 57.2 kills yr−1, [24]), female kill rates in the highest quartile of home range housing densities were substantially higher (81.2 kills yr−1). This 36% increase in kill rates between the top and bottom quartiles indicates that development may exert a significant energetic cost associated with hunting behaviour.

Hunting deer requires large energetic investments in the stalking, subduing and killing stages for pumas [16]. We have documented a sizable increase in female kill rates that we expect represents higher energetic costs for females in developed landscapes. Although these costs do not appear to influence adult survival (C. C. Wilmers 2014, unpublished data), impacts on reproductive success possibly make development-interface zones sinks for the puma population. Anecdotally, we have observed that the tagged female living in the most developed habitat in our study area has lost at least three litters in the last 3 years, one of which was confirmed as abandonment (C. C. Wilmers 2014, unpublished data). The three other females living in less developed portions of our study area for which we have also documented at least three dens have had the majority of their litters survive. Although there are many stressors in a developed landscape that might influence kitten survival, we expect that higher energetic costs from increased hunting may contribute to this pattern.

Males did not alter their kill rates or prey consumption time at kills with increasing housing density. Because male life histories are constrained by requirements to defend much larger territories [27], this is perhaps not surprising. We found that male pumas have home ranges that are approximately three times as large as female home ranges on average. Male pumas are also known to spend significantly more time performing scent-marking behaviours than females [28]. We found that males have lower DUR at kills than females by 7.2 h on average (males = 2.86 days ± 0.06 s.e., females = 2.56 days ± 0.05 s.e.; t = 3.83, d.f. = 1000, ), probably owing to their need to patrol and defend their home range boundaries from encroaching males. Therefore, because males already tend to leave their kills early, they may be less influenced by chronic disturbance. In addition, male home ranges are characterized by much lower overall housing densities, indicating that males may exhibit risk-avoidance behaviours at the landscape scale rather than at the kill site scale.

Higher deer kill rates by females in response to increased housing density appear to be driven by a behavioural shift to a lower proportion of time spent at kill sites over the consumption period. Although females did not alter their total duration spent at clusters, their overall prey consumption times declined owing to a lower proportion of time spent at kills, indicating reduced utilization of carcasses at higher housing densities. Other possible explanations for female increase in deer kill rate are not supported by our understanding of puma energetics and reproduction. Deer in our study have lower detection rates in more developed habitats (C. C. Wilmers 2014, unpublished data), therefore variation in deer activity or abundance is unlikely to explain these patterns. In addition, it is unlikely that increased kill rate could be a result of greater reproductive activity in high housing density areas because females in our study area avoid anthropogenic development when denning [10]. We conclude that behavioural risk avoidance is a substantial contributor to female prey consumption time and hence hunting patterns, due to our observation that housing density is associated with decreased prey consumption time. Both food loss and increased movement as a result of these behavioural shifts may contribute to observed increased kill rate in human-modified habitats.

An increase in ungulate carcasses left by female pumas may impact the biotic community by providing additional carrion subsidies to scavengers. By leaving their kills for longer periods of time in more developed areas, female pumas might create greater opportunity for scavenging by mesopredators and birds. Subordinate predators often scavenge kills of apex predators when kills are abandoned or not guarded [29], and carrion can form a large proportion of their diets [30]. Pumas are known to be important sources of food subsidies to mesopredators through carcass abandonment [31]. Our results suggest that mesopredator release may occur not only through the well-documented pathway of apex predator extirpations, but also via behaviour changes in extant apex predators leading to increased food provisioning. The presence of scavengers can exacerbate this pattern by reducing apex predator prey consumption time via food loss [17].

5. Conclusion

The results presented here have bearing on human-modified systems globally. Behavioural responses are often overlooked as ecosystem drivers in modified systems, overshadowed by population declines and extirpations. However, many species are able to persist in developing landscapes, but in an altered behavioural state. Our findings suggest a strong, perceivable impact of observed human-induced behavioural change on species interactions instigated by the presence of development. Risk aversion behaviours that result from anthropogenic disturbances are likely to restructure predator–prey interactions in a variety of contexts, given the large effects risk has been shown to have on foraging across taxa. Behaviour-mediated interactions are powerful forces in biotic systems, often playing an even more impactful role than consumptive interactions. A greater focus on behaviour-mediated effects of habitat alteration can further expand our understanding of community-level processes in human-modified systems.

Ethics statement

The study was carried out under the IACUC approval no. WILMC1011.

Data accessibility

Because pumas are a specially protected species in California, the location data are sensitive and have not been made accessible. However, the data can be available on request by contacting Justine A. Smith at jsmith5{at}ucsc.edu.

Author contributions

J.A.S. conceived the study, carried out the data analysis and drafted the manuscript. Y.W. assisted in project development and edited the manuscript. C.C.W. conceived and designed the overall study, supervised data collection, advised on data analysis and edited the manuscript.

Funding statement

Funding was provided by NSF grant nos. 0963022 and 1255913, as well as by the Gordon and Betty Moore Foundation, The Nature Conservancy, Midpeninsula Regional Open Space District, UC Santa Cruz and the Felidae Conservation Fund.

Conflict of interests

We have no competing interests.

Acknowledgements

We thank the California Department of Fish and Wildlife, Cliff Wylie, Dan Tichenor and Troy Collinsworth for their assistance in helping us capture pumas with hounds. We thank landowners who have allowed us to capture pumas and investigate kills. We thank P. Houghtaling for running our field team and V. Yovovich, Y. Shakeri, C. Fust, S. McCain, J. Kermish-Wells, L. Hibbler and dozens of undergraduate field and laboratory assistants for their contributions to data collection, entry and management.

  • Received November 4, 2014.
  • Accepted December 11, 2014.
References

Technical “whitepaper” for afl-fuzz

28 February 2015 - 8:00pm

=================================== Technical "whitepaper" for afl-fuzz =================================== This document provides a quick overview of the guts of American Fuzzy Lop. See http://lcamtuf.coredump.cx/afl/ for a description of what AFL is; README.txt for the general instruction manual; and for a discussion of motivations and design goals behind AFL, see related_work.txt. 0) Design statement ------------------- American Fuzzy Lop does its best not to focus on any singular principle of operation and not be a proof-of-concept for any specific theory. The tool can be thought of as a collection of hacks that have been tested in practice, found to be surprisingly effective, and have been implemented in the simplest, most robust way I could think of at the time. Many of the resulting features are made possible thanks to the availability of lightweight instrumentation that served as a foundation for the tool, but this mechanism should be though of merely as a means to an end. The only true governing principles are speed, reliability, and ease of use. This doc is probably the most formal account of the internals of AFL that I will write. 1) Coverage measurements ------------------------ The instrumentation injected into compiled programs captures branch (edge) coverage, along with coarse branch-taken hit counts. The code injected at branch points is essentially equivalent to: cur_location = ; shared_mem[cur_location ^ prev_location]++; prev_location = cur_location >> 1; The cur_location value is generated randomly to simplify the process of linking complex projects and keep the XOR output distributed uniformly. The shared_mem[] array is a 64 kB SHM region passed to the instrumented binary by the caller. Every byte set in the output map can be thought of as a hit for a particular (branch_src, branch_dst) tuple in the instrumented code. The size of the map is chosen so that collisions are sporadic with almost all of the intended targets, which usually sport between 2k and 10k discoverable branch points: Branch cnt | Colliding tuples | Example targets ------------+------------------+----------------- 1,000 | 0.75% | giflib, lzo 2,000 | 1.5% | zlib, tar, xz 5,000 | 3.5% | libpng, libwebp 10,000 | 7% | libxml 20,000 | 14% | sqlite 50,000 | 30% | - At the same time, its size is small enough to allow the map to be analyzed in a matter of microseconds on the receiving end, and to effortlessly fit within L2 cache. This form of coverage provides considerably more insight into the execution path of the program than simple block coverage. In particular, it trivially distinguishes between the following execution traces: A -> B -> C -> D -> E (tuples: AB, BC, CD, DE) A -> B -> D -> C -> E (tuples: AB, BD, DC, CE) This aids the discovery of subtle fault conditions in the underlying code, because security vulnerabilities are more often associated with unexpected or incorrect state transitions than with merely reaching a new basic block. The reason for the shift operation in the last line of the pseudocode shown earlier in this section is to preserve the directionality of tuples (without this, A ^ B would be indistinguishable from B ^ A) and to retain the identity of tight loops (otherwise, A ^ A would be obviously equal to B ^ B). The absence of simple saturating arithmetic opcodes on Intel CPUs means that the hit counters can sometimes wrap around to zero. Since this is a fairly unlikely and localized event, it's an acceptable performance trade-off. 2) Detecting new behaviors -------------------------- The fuzzer maintains a global map of tuples seen in previous executions; this data can be rapidly compared with individual traces and updated in just a couple of dword- or qword-wide instructions and a simple loop. When a mutated input produces an execution trace containing new tuples, the corresponding input file is preserved and routed for additional processing later on (see section #3). Inputs that do not trigger new local-scale state transitions in the execution trace are discarded, even if their overall instrumentation output pattern is unique. This approach allows for a very fine-grained and long-term exploration of program state while not having to perform any computationally intensive and fragile global comparisons of complex execution traces, and while avoiding the scourge of path explosion. To illustrate, consider that the second trace shown below would be considered substantially new because of the presence of new tuples (CA, AE): #1: A -> B -> C -> D -> E #2: A -> B -> C -> A -> E At the same time, with #2 processed, the following pattern will not be seen as unique, despite having a markedly different execution path: #3: A -> B -> C -> A -> B -> C -> A -> B -> C -> D -> E In addition to detecting new tuples, the fuzzer also considers coarse tuple hit counts. These are divided into several buckets: 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+ To some extent, the number of buckets is an implementation artifact: it allows an in-place mapping of an 8-bit counter generated by the instrumentation to an 8-position bitmap relied on by the fuzzer executable to keep track of the already-seen execution counts for each tuple. Changes within the range of a single bucket are ignored; transition from one bucket to another is flagged as an interesting change in program control flow, and are routed to the evolutionary process outlined in the section below. The hit count behavior provides a way to distinguish between potentially interesting control flow changes, such as a block of code being executed twice when it was normally hit only once. At the same time, it is fairly insensitive to empirically less notable changes, such as a loop going from 47 cycles to 48. The counters also provide some degree of "accidental" immunity against tuple collisions in dense trace maps. The execution is policed fairly heavily through memory and execution time limits; by default, the timeout is set at 5x the initially-calibrated execution speed, rounded up to 20 ms. The aggressive timeouts are meant to prevent dramatic fuzzer performance degradation by descending into tarpits that, say, improve coverage by 1% while being 100x slower; we pragmatically reject them and hope that the fuzzer will find a less expensive way to reach the same code. Empirical testing strongly suggests that more generous time limits are not worth the cost. 3) Evolving the input queue --------------------------- Mutated test cases that produced new state transitions within the program are added to the input queue and used as a starting point for future rounds of fuzzing. They supplement, but do not automatically replace, existing finds. This approach allows the tool to progressively explore various disjoint and possibly mutually incompatible features of the underlying data format, as shown in this image: http://lcamtuf.coredump.cx/afl/afl_gzip.png Several practical examples of the results of this algorithm are discussed here: http://lcamtuf.blogspot.com/2014/11/pulling-jpegs-out-of-thin-air.html http://lcamtuf.blogspot.com/2014/11/afl-fuzz-nobody-expects-cdata-sections.html The synthetic corpus produced by this process is essentially a compact collection of "hmm, this does something new!" input files, and can be used to seed any other testing processes down the line (for example, to manually stress-test resource-intensive desktop apps). With this approach, the queue for most targets grows to somewhere between 1k and 10k entries; approximately 10-30% of this is attributable to the discovery of new tuples, and the remainder is associated with changes in hit counts. The following table compares the relative ability to discover file syntax and explore program states when using several different approaches to guided fuzzing. The instrumented target was GNU patch 2.7.3 compiled with -O3 and seeded with a dummy text file; the session consisted of a single pass over the input queue with afl-fuzz: Fuzzer guidance | Blocks | Edges | Edge hit | Highest-coverage strategy used | reached | reached | cnt var | test case generated ------------------+---------+---------+----------+--------------------------- (Initial file) | 156 | 163 | 1.00 | (none) | | | | Blind fuzzing S | 182 | 205 | 2.23 | First 2 B of RCS diff Blind fuzzing L | 228 | 265 | 2.23 | First 4 B of -c mode diff Block coverage | 855 | 1,130 | 1.57 | Almost-valid RCS diff Edge coverage | 1,452 | 2,070 | 2.18 | One-chunk -c mode diff AFL model | 1,765 | 2,597 | 4.99 | Four-chunk -c mode diff The first entry for blind fuzzing ("S") corresponds to executing just a single round of testing; the second set of figures ("L") shows the fuzzer running in a loop for a number of execution cycles comparable with that of the instrumented runs, which required more time to fully process the queue. Roughly similar results have been obtained in a separate experiment where the fuzzer was modified to compile out all the random fuzzing stages and leave just a series of rudimentary, sequential operations such as walking bit flips. Because this mode would be incapable of altering the size of the input file, the sessions were seeded with a valid unified diff: Queue extension | Blocks | Edges | Edge hit | Number of unique strategy used | reached | reached | cnt var | crashes found ------------------+---------+---------+----------+------------------ (Initial file) | 624 | 717 | 1.00 | - | | | | Blind fuzzing | 1,101 | 1,409 | 1.60 | 0 Block coverage | 1,255 | 1,649 | 1.48 | 0 Edge coverage | 1,259 | 1,734 | 1.72 | 0 AFL model | 1,452 | 2,040 | 3.16 | 1 Some of the earlier work on evolutionary fuzzing suggested maintaining just a single test case and selecting for mutations that improve coverage. At least in the tests described above, this "greedy" method appeared to offer no substantial benefits over blind fuzzing. 4) Culling the corpus --------------------- The progressive state exploration approach outlined above means that some of the test cases synthesized later on in the game may have edge coverage that is a strict superset of the coverage provided by their ancestors. To optimize the fuzzing effort, AFL periodically re-evaluates the queue using a fast algorithm that selects a smaller subset of test cases that still cover every tuple seen so far, and whose characteristics make them particularly favorable to the tool. The algorithm works by assigning every queue entry a score proportional to its execution latency and file size; and then selecting lowest-scoring candidates for each tuple. The tuples are then processed sequentially using a simple workflow: 1) Find next tuple not yet in the temporary working set, 2) Locate the winning queue entry for this tuple, 3) Register *all* tuples present in that entry's trace in the working set, 4) Go to #1 if there are any missing tuples in the set. The generated corpus of "favored" entries is usually 5-10x smaller than the starting data set. Non-favored entries are not discarded, but they are skipped with varying probabilities when encountered in the queue: - If there are new, yet-to-be-fuzzed favorites present in the queue, 99% of non-favored entries will be skipped to get to the favored ones. - If there are no new favorites: - If the current non-favored entry was fuzzed before, it will be skipped 95% of the time. - If it hasn't gone through any fuzzing rounds yet, the odds of skipping drop down to 75%. Based on empirical testing, this provides a reasonable balance between queue cycling speed and test case diversity. Slightly more sophisticated but much slower culling can be performed on input or output corpora with afl-cmin. This tool permanently discards the redundant entries and produces a smaller corpus suitable for use with afl-fuzz or external tools. 5) Trimming input files ----------------------- File size has a dramatic impact on fuzzing performance, both because large files make the target binary slower, and because they reduce the likelihood that a mutation would touch important format control structures, rather than redundant data blocks. This is discussed in more detail in perf_tips.txt. The possibility of a bad starting corpus provided by the user aside, some types of mutations can have the effect of iteratively increasing the size of the generated files, so it is important to counter this trend. Luckily, the instrumentation feedback provides a simple way to automatically trim down input files while ensuring that the changes made to the files have no impact on the execution path. The built-in trimmer in afl-fuzz attempts to sequentially remove blocks of data with variable length and stepover; any deletion that doesn't affect the checksum of the trace map is committed to disk. The trimmer is not designed to be particularly thorough; instead, it tries to strike a balance between precision and the number of execve() calls spent on the process. The average per-file gains are around 5-20%. The standalone afl-tmin tool uses a more exhaustive, iterative algorithm, and also attempts to perform alphabet normalization on the trimmed files. 6) Fuzzing strategies --------------------- The feedback provided by the instrumentation makes it easy to understand the value of various fuzzing strategies and optimize their parameters so that they work equally well across a wide range of file types. The strategies used by afl-fuzz are generally format-agnostic and are discussed in more detail here: http://lcamtuf.blogspot.com/2014/08/binary-fuzzing-strategies-what-works.html It is somewhat notable that especially early on, most of the work done by afl-fuzz is actually highly deterministic, and progresses to random stacked modifications and test case splicing only at a later stage. The deterministic strategies include: - Sequential bit flips with varying lengths and stepovers, - Sequential addition and subtraction of small integers, - Sequential insertion of known interesting integers (0, 1, INT_MAX, etc), The non-deterministic steps include stacked bit flips, insertions, deletions, arithmetics, and splicing of different test cases. Their relative yields and execve() costs have been investigated and are discussed in the aforementioned blog post. For the reasons discussed in related_work.txt (chiefly, performance, simplicity, and reliability), AFL generally does not try to reason about the relationship between specific mutations and program states; the fuzzing steps are nominally blind, and are guided only by the evolutionary design of the input queue. That said, there is one (trivial) exception to this rule: when a new queue entry goes through the initial set of deterministic fuzzing steps, and some regions in the file are observed to have no effect on the checksum of the execution path, they may be excluded from the remaining phases of deterministic fuzzing - and proceed straight to random tweaks. Especially for verbose, human-readable data formats, this can reduce the number of execs by 10-40% or so without an appreciable drop in coverage. In extreme cases, such as normally block-aligned tar archives, the gains can be as high as 90%. Because the underlying "effector maps" are local every queue entry and remain in force only during deterministic stages that do not alter the size or the general layout of the underlying file, this mechanism appears to work very reliably and proved to be simple to implement. 7) Dictionaries --------------- The feedback provided by the instrumentation makes it easy to automatically identify syntax tokens in some types of input files, and to detect that certain combinations of predefined or auto-detected dictionary terms constitute a valid grammar for the tested parser. A discussion of how these features are implemented within afl-fuzz can be found here: http://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html In essence, when basic, typically easily-obtained syntax tokens are combined together in a purely random manner, the instrumentation and the evolutionary design of the queue together provide a feedback mechanism to differentiate between meaningless mutations and ones that trigger new behaviors in the instrumented code - and to incrementally build more complex syntax on top of this discovery. The dictionaries have been shown to enable the fuzzer to rapidly reconstruct the grammar of highly verbose and complex languages such as JavaScript, SQL, or XML; several examples of generated SQL statements are given in the blog post mentioned above. 8) De-duping crashes -------------------- De-duplication of crashes is one of the more important problems for any competent fuzzing tool. Many of the naive approaches run into problems; in particular, looking just at the faulting address may lead to completely unrelated issues being clustered together if the fault happens in a common library function (say, strcmp, strcpy); while checksumming call stack backtraces can lead to extreme crash count inflation if the fault can be reached through a number of different, possibly recursive code paths. The solution implemented in afl-fuzz considers a crash unique if any of two conditions are met: - The crash trace includes a tuple not seen in any of the previous crashes, - The crash trace is missing a tuple that was always present in earlier faults. The approach is vulnerable to some path count inflation early on, but exhibits a very strong self-limiting effect, similar to the execution path analysis logic that is the cornerstone of afl-fuzz. 9) Investigating crashes ------------------------ The exploitability of many types of crashes can be ambiguous; afl-fuzz tries to address this by providing a crash exploration mode where a known-faulting test case is fuzzed in a manner very similar to the normal operation of the fuzzer, but with a constraint that causes any non-crashing mutations to be thrown away. A detailed discussion of the value of this approach can be found here: http://lcamtuf.blogspot.com/2014/11/afl-fuzz-crash-exploration-mode.html The method uses instrumentation feedback to explore the state of the crashing program to get past the ambiguous faulting condition and then isolate the newly-found inputs for human review. On the subject of crashes, it is worth noting that in contrast to normal queue entries, crashing inputs are *not* trimmed; they are kept exactly as discovered to make it easier to compare them to the parent, non-crashing entry in the queue. That said, afl-tmin can be used to shrink them at will. 10) The fork server ------------------- To improve performance, afl-fuzz uses a "fork server", where the fuzzed process goes through execve(), linking, and libc initialization only once, and is then cloned from a stopped process image by leveraging copy-on-write. The implementation is described in more detail here: http://lcamtuf.blogspot.com/2014/10/fuzzing-binaries-without-execve.html The fork server is an integral aspect of the injected instrumentation and simply stops at the first instrumented function to await commands from afl-fuzz. With fast targets, the fork server can offer considerable performance gains, usually between 1.5x and 2x. 11) Parallelization ------------------- The parallelization mechanism relies on periodically examining the queues produced by independently-running instances on other CPU cores or on remote machines, and then selectively pulling in the test cases that produce behaviors not yet seen by the fuzzer at hand. This allows for extreme flexibility in fuzzer setup, including running synced instances against different parsers of a common data format, often with synergistic effects. For more information about this design, see parallel_fuzzing.txt. 12) Binary-only instrumentation ------------------------------- Instrumentation of black-box, binary-only targets is accomplished with the help of a separately-built version of QEMU in "user emulation" mode. This also allows the execution of cross-architecture code - say, ARM binaries on x86. QEMU uses basic blocks as translation units; the instrumentation is implemented on top of this and uses a model roughly analogous to the compile-time hooks: if (block_address > elf_text_start && block_address < elf_text_end) { cur_location = (block_address >> 4) ^ (block_address << 8); shared_mem[cur_location ^ prev_location]++; prev_location = cur_location >> 1; } The shift-and-XOR-based scrambling in the second line is used to mask the effects of instruction alignment. The start-up of binary translators such as QEMU, DynamoRIO, and PIN is fairly slow; to counter this, the QEMU mode leverages a fork server similar to that used for compiler-instrumented code, effectively spawning copies of an already-initialized process paused at _start. First-time translation of a new basic block also incurs substantial latency. To eliminate this problem, the AFL fork server is extended by providing a channel between the running emulator and the parent process. The channel is used to notify the parent about the addresses of any newly-encountered blocks and to add them to the translation cache that will be replicated for future child processes. As a result of these two optimizations, the overhead of the QEMU mode is roughly 2-5x, compared to 100x+ for PIN.

=================================== Technical "whitepaper" for afl-fuzz =================================== This document provides a quick overview of the guts of American Fuzzy Lop. See http://lcamtuf.coredump.cx/afl/ for a description of what AFL is; README.txt for the general instruction manual; and for a discussion of motivations and design goals behind AFL, see related_work.txt. 0) Design statement ------------------- American Fuzzy Lop does its best not to focus on any singular principle of operation and not be a proof-of-concept for any specific theory. The tool can be thought of as a collection of hacks that have been tested in practice, found to be surprisingly effective, and have been implemented in the simplest, most robust way I could think of at the time. Many of the resulting features are made possible thanks to the availability of lightweight instrumentation that served as a foundation for the tool, but this mechanism should be though of merely as a means to an end. The only true governing principles are speed, reliability, and ease of use. This doc is probably the most formal account of the internals of AFL that I will write. 1) Coverage measurements ------------------------ The instrumentation injected into compiled programs captures branch (edge) coverage, along with coarse branch-taken hit counts. The code injected at branch points is essentially equivalent to: cur_location = ; shared_mem[cur_location ^ prev_location]++; prev_location = cur_location >> 1; The cur_location value is generated randomly to simplify the process of linking complex projects and keep the XOR output distributed uniformly. The shared_mem[] array is a 64 kB SHM region passed to the instrumented binary by the caller. Every byte set in the output map can be thought of as a hit for a particular (branch_src, branch_dst) tuple in the instrumented code. The size of the map is chosen so that collisions are sporadic with almost all of the intended targets, which usually sport between 2k and 10k discoverable branch points: Branch cnt | Colliding tuples | Example targets ------------+------------------+----------------- 1,000 | 0.75% | giflib, lzo 2,000 | 1.5% | zlib, tar, xz 5,000 | 3.5% | libpng, libwebp 10,000 | 7% | libxml 20,000 | 14% | sqlite 50,000 | 30% | - At the same time, its size is small enough to allow the map to be analyzed in a matter of microseconds on the receiving end, and to effortlessly fit within L2 cache. This form of coverage provides considerably more insight into the execution path of the program than simple block coverage. In particular, it trivially distinguishes between the following execution traces: A -> B -> C -> D -> E (tuples: AB, BC, CD, DE) A -> B -> D -> C -> E (tuples: AB, BD, DC, CE) This aids the discovery of subtle fault conditions in the underlying code, because security vulnerabilities are more often associated with unexpected or incorrect state transitions than with merely reaching a new basic block. The reason for the shift operation in the last line of the pseudocode shown earlier in this section is to preserve the directionality of tuples (without this, A ^ B would be indistinguishable from B ^ A) and to retain the identity of tight loops (otherwise, A ^ A would be obviously equal to B ^ B). The absence of simple saturating arithmetic opcodes on Intel CPUs means that the hit counters can sometimes wrap around to zero. Since this is a fairly unlikely and localized event, it's an acceptable performance trade-off. 2) Detecting new behaviors -------------------------- The fuzzer maintains a global map of tuples seen in previous executions; this data can be rapidly compared with individual traces and updated in just a couple of dword- or qword-wide instructions and a simple loop. When a mutated input produces an execution trace containing new tuples, the corresponding input file is preserved and routed for additional processing later on (see section #3). Inputs that do not trigger new local-scale state transitions in the execution trace are discarded, even if their overall instrumentation output pattern is unique. This approach allows for a very fine-grained and long-term exploration of program state while not having to perform any computationally intensive and fragile global comparisons of complex execution traces, and while avoiding the scourge of path explosion. To illustrate, consider that the second trace shown below would be considered substantially new because of the presence of new tuples (CA, AE): #1: A -> B -> C -> D -> E #2: A -> B -> C -> A -> E At the same time, with #2 processed, the following pattern will not be seen as unique, despite having a markedly different execution path: #3: A -> B -> C -> A -> B -> C -> A -> B -> C -> D -> E In addition to detecting new tuples, the fuzzer also considers coarse tuple hit counts. These are divided into several buckets: 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+ To some extent, the number of buckets is an implementation artifact: it allows an in-place mapping of an 8-bit counter generated by the instrumentation to an 8-position bitmap relied on by the fuzzer executable to keep track of the already-seen execution counts for each tuple. Changes within the range of a single bucket are ignored; transition from one bucket to another is flagged as an interesting change in program control flow, and are routed to the evolutionary process outlined in the section below. The hit count behavior provides a way to distinguish between potentially interesting control flow changes, such as a block of code being executed twice when it was normally hit only once. At the same time, it is fairly insensitive to empirically less notable changes, such as a loop going from 47 cycles to 48. The counters also provide some degree of "accidental" immunity against tuple collisions in dense trace maps. The execution is policed fairly heavily through memory and execution time limits; by default, the timeout is set at 5x the initially-calibrated execution speed, rounded up to 20 ms. The aggressive timeouts are meant to prevent dramatic fuzzer performance degradation by descending into tarpits that, say, improve coverage by 1% while being 100x slower; we pragmatically reject them and hope that the fuzzer will find a less expensive way to reach the same code. Empirical testing strongly suggests that more generous time limits are not worth the cost. 3) Evolving the input queue --------------------------- Mutated test cases that produced new state transitions within the program are added to the input queue and used as a starting point for future rounds of fuzzing. They supplement, but do not automatically replace, existing finds. This approach allows the tool to progressively explore various disjoint and possibly mutually incompatible features of the underlying data format, as shown in this image: http://lcamtuf.coredump.cx/afl/afl_gzip.png Several practical examples of the results of this algorithm are discussed here: http://lcamtuf.blogspot.com/2014/11/pulling-jpegs-out-of-thin-air.html http://lcamtuf.blogspot.com/2014/11/afl-fuzz-nobody-expects-cdata-sections.html The synthetic corpus produced by this process is essentially a compact collection of "hmm, this does something new!" input files, and can be used to seed any other testing processes down the line (for example, to manually stress-test resource-intensive desktop apps). With this approach, the queue for most targets grows to somewhere between 1k and 10k entries; approximately 10-30% of this is attributable to the discovery of new tuples, and the remainder is associated with changes in hit counts. The following table compares the relative ability to discover file syntax and explore program states when using several different approaches to guided fuzzing. The instrumented target was GNU patch 2.7.3 compiled with -O3 and seeded with a dummy text file; the session consisted of a single pass over the input queue with afl-fuzz: Fuzzer guidance | Blocks | Edges | Edge hit | Highest-coverage strategy used | reached | reached | cnt var | test case generated ------------------+---------+---------+----------+--------------------------- (Initial file) | 156 | 163 | 1.00 | (none) | | | | Blind fuzzing S | 182 | 205 | 2.23 | First 2 B of RCS diff Blind fuzzing L | 228 | 265 | 2.23 | First 4 B of -c mode diff Block coverage | 855 | 1,130 | 1.57 | Almost-valid RCS diff Edge coverage | 1,452 | 2,070 | 2.18 | One-chunk -c mode diff AFL model | 1,765 | 2,597 | 4.99 | Four-chunk -c mode diff The first entry for blind fuzzing ("S") corresponds to executing just a single round of testing; the second set of figures ("L") shows the fuzzer running in a loop for a number of execution cycles comparable with that of the instrumented runs, which required more time to fully process the queue. Roughly similar results have been obtained in a separate experiment where the fuzzer was modified to compile out all the random fuzzing stages and leave just a series of rudimentary, sequential operations such as walking bit flips. Because this mode would be incapable of altering the size of the input file, the sessions were seeded with a valid unified diff: Queue extension | Blocks | Edges | Edge hit | Number of unique strategy used | reached | reached | cnt var | crashes found ------------------+---------+---------+----------+------------------ (Initial file) | 624 | 717 | 1.00 | - | | | | Blind fuzzing | 1,101 | 1,409 | 1.60 | 0 Block coverage | 1,255 | 1,649 | 1.48 | 0 Edge coverage | 1,259 | 1,734 | 1.72 | 0 AFL model | 1,452 | 2,040 | 3.16 | 1 Some of the earlier work on evolutionary fuzzing suggested maintaining just a single test case and selecting for mutations that improve coverage. At least in the tests described above, this "greedy" method appeared to offer no substantial benefits over blind fuzzing. 4) Culling the corpus --------------------- The progressive state exploration approach outlined above means that some of the test cases synthesized later on in the game may have edge coverage that is a strict superset of the coverage provided by their ancestors. To optimize the fuzzing effort, AFL periodically re-evaluates the queue using a fast algorithm that selects a smaller subset of test cases that still cover every tuple seen so far, and whose characteristics make them particularly favorable to the tool. The algorithm works by assigning every queue entry a score proportional to its execution latency and file size; and then selecting lowest-scoring candidates for each tuple. The tuples are then processed sequentially using a simple workflow: 1) Find next tuple not yet in the temporary working set, 2) Locate the winning queue entry for this tuple, 3) Register *all* tuples present in that entry's trace in the working set, 4) Go to #1 if there are any missing tuples in the set. The generated corpus of "favored" entries is usually 5-10x smaller than the starting data set. Non-favored entries are not discarded, but they are skipped with varying probabilities when encountered in the queue: - If there are new, yet-to-be-fuzzed favorites present in the queue, 99% of non-favored entries will be skipped to get to the favored ones. - If there are no new favorites: - If the current non-favored entry was fuzzed before, it will be skipped 95% of the time. - If it hasn't gone through any fuzzing rounds yet, the odds of skipping drop down to 75%. Based on empirical testing, this provides a reasonable balance between queue cycling speed and test case diversity. Slightly more sophisticated but much slower culling can be performed on input or output corpora with afl-cmin. This tool permanently discards the redundant entries and produces a smaller corpus suitable for use with afl-fuzz or external tools. 5) Trimming input files ----------------------- File size has a dramatic impact on fuzzing performance, both because large files make the target binary slower, and because they reduce the likelihood that a mutation would touch important format control structures, rather than redundant data blocks. This is discussed in more detail in perf_tips.txt. The possibility of a bad starting corpus provided by the user aside, some types of mutations can have the effect of iteratively increasing the size of the generated files, so it is important to counter this trend. Luckily, the instrumentation feedback provides a simple way to automatically trim down input files while ensuring that the changes made to the files have no impact on the execution path. The built-in trimmer in afl-fuzz attempts to sequentially remove blocks of data with variable length and stepover; any deletion that doesn't affect the checksum of the trace map is committed to disk. The trimmer is not designed to be particularly thorough; instead, it tries to strike a balance between precision and the number of execve() calls spent on the process. The average per-file gains are around 5-20%. The standalone afl-tmin tool uses a more exhaustive, iterative algorithm, and also attempts to perform alphabet normalization on the trimmed files. 6) Fuzzing strategies --------------------- The feedback provided by the instrumentation makes it easy to understand the value of various fuzzing strategies and optimize their parameters so that they work equally well across a wide range of file types. The strategies used by afl-fuzz are generally format-agnostic and are discussed in more detail here: http://lcamtuf.blogspot.com/2014/08/binary-fuzzing-strategies-what-works.html It is somewhat notable that especially early on, most of the work done by afl-fuzz is actually highly deterministic, and progresses to random stacked modifications and test case splicing only at a later stage. The deterministic strategies include: - Sequential bit flips with varying lengths and stepovers, - Sequential addition and subtraction of small integers, - Sequential insertion of known interesting integers (0, 1, INT_MAX, etc), The non-deterministic steps include stacked bit flips, insertions, deletions, arithmetics, and splicing of different test cases. Their relative yields and execve() costs have been investigated and are discussed in the aforementioned blog post. For the reasons discussed in related_work.txt (chiefly, performance, simplicity, and reliability), AFL generally does not try to reason about the relationship between specific mutations and program states; the fuzzing steps are nominally blind, and are guided only by the evolutionary design of the input queue. That said, there is one (trivial) exception to this rule: when a new queue entry goes through the initial set of deterministic fuzzing steps, and some regions in the file are observed to have no effect on the checksum of the execution path, they may be excluded from the remaining phases of deterministic fuzzing - and proceed straight to random tweaks. Especially for verbose, human-readable data formats, this can reduce the number of execs by 10-40% or so without an appreciable drop in coverage. In extreme cases, such as normally block-aligned tar archives, the gains can be as high as 90%. Because the underlying "effector maps" are local every queue entry and remain in force only during deterministic stages that do not alter the size or the general layout of the underlying file, this mechanism appears to work very reliably and proved to be simple to implement. 7) Dictionaries --------------- The feedback provided by the instrumentation makes it easy to automatically identify syntax tokens in some types of input files, and to detect that certain combinations of predefined or auto-detected dictionary terms constitute a valid grammar for the tested parser. A discussion of how these features are implemented within afl-fuzz can be found here: http://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html In essence, when basic, typically easily-obtained syntax tokens are combined together in a purely random manner, the instrumentation and the evolutionary design of the queue together provide a feedback mechanism to differentiate between meaningless mutations and ones that trigger new behaviors in the instrumented code - and to incrementally build more complex syntax on top of this discovery. The dictionaries have been shown to enable the fuzzer to rapidly reconstruct the grammar of highly verbose and complex languages such as JavaScript, SQL, or XML; several examples of generated SQL statements are given in the blog post mentioned above. 8) De-duping crashes -------------------- De-duplication of crashes is one of the more important problems for any competent fuzzing tool. Many of the naive approaches run into problems; in particular, looking just at the faulting address may lead to completely unrelated issues being clustered together if the fault happens in a common library function (say, strcmp, strcpy); while checksumming call stack backtraces can lead to extreme crash count inflation if the fault can be reached through a number of different, possibly recursive code paths. The solution implemented in afl-fuzz considers a crash unique if any of two conditions are met: - The crash trace includes a tuple not seen in any of the previous crashes, - The crash trace is missing a tuple that was always present in earlier faults. The approach is vulnerable to some path count inflation early on, but exhibits a very strong self-limiting effect, similar to the execution path analysis logic that is the cornerstone of afl-fuzz. 9) Investigating crashes ------------------------ The exploitability of many types of crashes can be ambiguous; afl-fuzz tries to address this by providing a crash exploration mode where a known-faulting test case is fuzzed in a manner very similar to the normal operation of the fuzzer, but with a constraint that causes any non-crashing mutations to be thrown away. A detailed discussion of the value of this approach can be found here: http://lcamtuf.blogspot.com/2014/11/afl-fuzz-crash-exploration-mode.html The method uses instrumentation feedback to explore the state of the crashing program to get past the ambiguous faulting condition and then isolate the newly-found inputs for human review. On the subject of crashes, it is worth noting that in contrast to normal queue entries, crashing inputs are *not* trimmed; they are kept exactly as discovered to make it easier to compare them to the parent, non-crashing entry in the queue. That said, afl-tmin can be used to shrink them at will. 10) The fork server ------------------- To improve performance, afl-fuzz uses a "fork server", where the fuzzed process goes through execve(), linking, and libc initialization only once, and is then cloned from a stopped process image by leveraging copy-on-write. The implementation is described in more detail here: http://lcamtuf.blogspot.com/2014/10/fuzzing-binaries-without-execve.html The fork server is an integral aspect of the injected instrumentation and simply stops at the first instrumented function to await commands from afl-fuzz. With fast targets, the fork server can offer considerable performance gains, usually between 1.5x and 2x. 11) Parallelization ------------------- The parallelization mechanism relies on periodically examining the queues produced by independently-running instances on other CPU cores or on remote machines, and then selectively pulling in the test cases that produce behaviors not yet seen by the fuzzer at hand. This allows for extreme flexibility in fuzzer setup, including running synced instances against different parsers of a common data format, often with synergistic effects. For more information about this design, see parallel_fuzzing.txt. 12) Binary-only instrumentation ------------------------------- Instrumentation of black-box, binary-only targets is accomplished with the help of a separately-built version of QEMU in "user emulation" mode. This also allows the execution of cross-architecture code - say, ARM binaries on x86. QEMU uses basic blocks as translation units; the instrumentation is implemented on top of this and uses a model roughly analogous to the compile-time hooks: if (block_address > elf_text_start && block_address < elf_text_end) { cur_location = (block_address >> 4) ^ (block_address << 8); shared_mem[cur_location ^ prev_location]++; prev_location = cur_location >> 1; } The shift-and-XOR-based scrambling in the second line is used to mask the effects of instruction alignment. The start-up of binary translators such as QEMU, DynamoRIO, and PIN is fairly slow; to counter this, the QEMU mode leverages a fork server similar to that used for compiler-instrumented code, effectively spawning copies of an already-initialized process paused at _start. First-time translation of a new basic block also incurs substantial latency. To eliminate this problem, the AFL fork server is extended by providing a channel between the running emulator and the parent process. The channel is used to notify the parent about the addresses of any newly-encountered blocks and to add them to the translation cache that will be replicated for future child processes. As a result of these two optimizations, the overhead of the QEMU mode is roughly 2-5x, compared to 100x+ for PIN.