Providence: Matching people to jobs

This post is part of a series on the Providence project at Stack Exchange, the first post can be found here.

We’ve gone over building the “developer-kind” and “technology”  classifiers, but we’ve yet to describe actually using these predictions for anything.  We started with better targeting for Stack Overflow Careers job listings, this was an attractive place to start because our existing system was very naïve, there was enough volume to run experiments easily, and mistakes wouldn’t be very harmful to our users.

The Challenge

In a nutshell, the challenge was: given a person and a set of job listings, produce a prediction of how well the person “fits” each of the jobs.  We wanted to produce a value for each job-person pair, rather than just picking some number of jobs for a person, so we could experiment independently in the final ad selection approaches.

To quickly recap what we had to work with: for each person who visits Stack Overflow, we had 11 developer-kind percentage labels, 15 technology percentage labels, and the tag view data which was used to generate those sets of labels; for each job listed on Stack Overflow Careers, we had a list of preferred developer-kinds, preferred technologies, and some tags related to the job.

When designing this algorithm, there were a few goals we had to keep in mind.  Neither overly broad jobs (ie. “Web Developer, Any Platform”) nor overly narrow jobs (ie. “ASP.NET MVC2, EF4, and F# in Brownsville”) should dominate.  Similarly, while no single label should overwhelm the others, the algorithm should incorporate knowledge of how significant our experimentation revealed the different labels to be.  This algorithm was also one of the few pieces of Providence that needed to run in real time.

The Algorithm

The end result was very simple, and can be broken down into the following steps:

1. Mask away any developer-kind and technology labels on the person that are not also in the job
   1. So a job without “Android Developer” will ignore that label on the person
2. Sum each developer-kind percentage label that remains
3. Sum each technology percentage label that remains
4. Determine the tag the person is most active in which also appears on the job, if any
5. Calculate what percentage of a person’s overall tag activity occurred in the tag chosen in the previous step
6. Scale the percentages calculated in steps 3, 4, & 5 by some pre-calculated weights (see below) and sum them
7. Determine the largest possible value that could have been calculated in step 6
8. Divide the value of step 6 by the value in step 7, producing our final result

Conceptually, the above algorithm determines the features of a person who would be perfect for a job, and then determine how closely the actual person we’re considering matches.

The per-feature weights it incorporates let us emphasize that certain features are better predictors of a match than others.  The least predictive feature is developer-kind, so it is given a weight of one, while technologies and tag matches have weights of two and three because they are roughly two and three times as predictive, respectively.  We determined the weight for each feature with experiments in which each feature was used alone to target ads, then compared the relative improvement observed for each feature.  These weights also matched our intuition; it makes sense that being a Full Stack Web Developer instead of a Back End Web Developer doesn’t matter as much as being unfamiliar with the technology stack, which itself isn’t as significant as lacking the domain knowledge implied by a particular tag.

Once we tested this algorithm and determined it worked, we had to decide what to do when it didn’t have enough information to make any intelligent predictions.  This can happen in two cases: if we know nothing about the user (if they’re brand new, or have opted-out of Providence), and if we know nothing about the job (it may be a crazy outlier, badly entered, or just plain a bad job).  In both cases we decided to predict a low, but non-zero, default value; this means that an “empty” person will still get a reasonable mix of jobs and that an “empty” job will still get some exposure.  This default value was selected by randomly sampling people and averaging how well they match all the non-empty jobs we’ve ever seen, then adjusting that average down by one standard deviation.  In practice, this means the default ranks somewhere between 30% and 50% of the non-empty matches calculated for most users.

There were a few non-Providence concerns to handle after nailing down this algorithm before we could ship the final product.  We needed to constrain ads geographically, chose a subset of ads based on their predicted weights, and serve the actual ads on Stack Overflow.  All of these were left to our ad server team, and dealt with without resorting to any machine learning trickery.

That wraps up the particularly data and machine learning-focused bits of Providence, but this isn’t the last post. Jason Punyon will continue the series over on his blog.

Next up:  All the testing we did, and what we learned from it

Providence: What technologies do you know?

This post is part of a series on the Providence project at Stack Exchange, the first post can be found here.

Having already built a classifier for “developer-kinds”, we next set out to determine what technologies people are using.  What we considered to be distinct technologies are things like “Microsoft’s web stack” or “Oracle’s database servers,” which are coarser groupings than say “ASP.NET” or “Oracle 11g.”

It was tempting to consider these technologies to be more specific developer-kinds, but we found that many people are knowledgeable about several technologies even if they specialize in only one or two kinds of development.  For example, many developers are at least passingly familiar with PHP web development even if they may be exclusively writing iOS apps for the time being.

The Data

Our starting point for this problem was to determine what technologies are both actually out there and used by large segments of the developer population.  We got the list of technologies by looking at the different job openings listed on Stack Overflow Careers for which companies are trying to hire developers. This was a decent enough proxy for our purposes.  After excluding a few labels for being too ambiguous, we settled on the following list:

• PHP
• Ruby On Rails
• Microsoft’s Web Stack (ASP.NET, IIS, etc.)
• Node.js
• Python’s Web Stacks (Django, Flask, etc.)
• Java’s Web Stacks (JSP, Struts, etc.)
• WordPress
• Cloud Platforms (Azure, EC2, etc.)
• Salesforce
• SharePoint
• Windows
• OS X
• Oracle RDBMS
• Microsoft SQL Server
• MySQL

Something that stands out in these labels is the prevalence of Microsoft technologies.  We suspect this is a consequence of two factors: Microsoft’s reach is very broad due to its historical dominance of the industry, and Stack Overflow itself (and thus the jobs listed on Careers Stack Overflow) has a slight Microsoft bias due to early users being predominantly Coding Horror and Joel On Software readers.

Furthermore, mobile technologies are unrepresented in the list, likely because they are already adequately covered by the developer-kind predictions.  The reality on the ground is that developing for a particular mobile platform very strongly implies the use of particular technologies.  While some people do use things like Xamarin or Ruby Motion to develop for iOS and Android, the vast majority do not.

The Classifier

We knew that many tags on Stack Overflow correlate strongly with a particular technology, but others, such as [sql], were split between several different technologies.  To determine these relationships, we looked at tag co-occurrence on questions.  For example, given that [jsp] is a Java Web Stacks tag which co-occurs quite a bit more with [java] than [windows] tells us that viewing a question with the [java] should count more towards the “Java Web Stacks” technologies than the “Windows” technologies.  Repeatedly applying this observation allowed us to grow clouds of related tags, each with a weight proportional to their co-occurrence with tags of a known quality.  One small tweak over this simple system was to reduce the weights of tags that are commonly found in several technologies, such as [sql] which co-occurs with many different database, application, and web technologies.

This approach required that we hand-select seed tags for each technology.  The seeds used in the first version of Providence for each technology are:

• PHP – php, php-*, zend-framework
• Ruby On Rails – ruby-on-rails, ruby-on-rails-*, active-record
• Microsoft’s Web Stack – asp.net, asp.net-*, iis, iis-*
• Node.js – node.js, node.js-*, express, npm, meteor
• Python’s Web Stacks – django, django-*, google-app-engine, flask, flask-*
• Java’s Web Stacks – jsp, jsp-*, jsf, jsf-*, facelets, primefaces, servlets, java-ee, struts*, spring-mvc, tomcat
• WordPress – wordpress, wordpress-*
• Cloud Platforms – cloud, azure, amazon-ec2, amazon-web-services, amazon-s3
• Salesforce – salesforce, salesforce-*
• SharePoint – sharepoint, sharepoint-*, wss, wss-*
• Windows – windows, windows-*, winapi, winforms
• OS X – osx, osx-*, cocoa, applescript
• Oracle RDBMS – oracle, oracle*, plsql
• Microsoft SQL Server – sql-server, sql-server-*, tsql
• MySQL – mysql, phpmyadmin

By this point, the technology classifier was functionally complete, but in order to reduce some noise in our predictions, we decided to constrain the number of tags we consider to 500 per technology and ignore any tags that are used on less than 0.05% of Stack Overflow questions.

Next up: Actually using Providence for something useful

Providence: Machine Learning At Stack Exchange

At Stack Exchange, we’ve historically been pretty loose with our data analysis.  You can see this in the “answered questions” definition (has an accepted answer or an answer with score > 0), “question quality” (measured by ad hoc heuristics based on votes, length, and character classes), “interesting tab” homepage algorithm (backed by a series of experimentally determined weights), and rather naïve question search function.

This approach has worked for a long time (turns out your brain is a great tool for data analysis), but as our community grows and we tackle more difficult problems we’ve needed to become more sophisticated.  For example, we didn’t have to worry about matching users to questions when we only had 30 questions a day but 3,500 a day is a completely different story.  Some of our efforts to address these problems have already shipped, such as a more sophisticated homepage algorithm, while others are still ongoing, such as improvements to our search and quality scoring.

One of our other efforts is to better understand our users, which led to the Providence project.  Providence analyzes our traffic logs to predict some simple labels (like “is a web developer” or “uses the Java technology stack”) for each person who visits our site.  In its early incarnation, we only have a few labels but we’re planning to continue adding new labels in order to build new features and improve old ones.

While we can’t release the Stack Overflow traffic logs for privacy reasons, we believe it’s in the best interest of the community for us to document the ways we’re using it.  Accordingly, this is the first post in a series on the Providence project.  We’re going to cover each of the individual predictions made, as well as architecture, testing, and all the little (and not-so-little) problems we had shipping version 1.0.

We have also added a way for any user to download their current Providence prediction data because it’s theirs and they should be able to see and use it as they like.  Users can also prevent other systems (Careers, the Stack Overflow homepage, etc.) from querying their Providence data if they want to.

First up: What kind of developer are you?

One of the first questions we wanted Providence to answer was ‘What “kind” of developer are you?’.  This larger question also encompassed sub-questions:

• What are the different “developer-kinds”?
• How much, if at all, do people specialize in a single “kind” of development?
• Among these different kinds of developers, do they use Stack Overflow differently?

We answered the first sub-question by looking at a lots and lots of résumés and job postings.  While there is definitely a fair amount of fuzziness in job titles, there’s a loose consensus on the sorts of developers out there.  After filtering out some labels for which we just didn’t have much data (more on that later), we came up with this list of developer-kinds:

• Full Stack Web Developers
• Front End Web Developers
• Back End Web Developers
• Android Developers
• iOS Developers
• Windows Phone Developers
• Database Administrators
• System Administrators
• Desktop Developers
• Math/Statistics Focused Developers
• Graphics Developers

The second sub-question we answered by looking at typical users of Stack Overflow.  Our conclusion was that although many jobs are fairly specialized, few developers focus on a single role to the exclusion of all else.  This matched our intuition, because it’s pretty hard to avoid exposure to at least some web technologies, not to mention developers love to tinker with new things for the heck of it.

Answering the final sub-question was nothing short of a leap of faith.  We assumed that different kinds of developers viewed different sets of questions; and, as all we had to use were traffic logs, we couldn’t really test any other assumptions anyway.  Having moved forward regardless, we now know that we were correct, but at the time we were taking a gamble.

The Data

A prerequisite for any useful analysis is data, and for our developer-kind predictions we needed labeled data.  Seeing that Providence did not yet exist, this data had not been gathered.  This is a chicken and egg problem that frequently popped up during the Providence project.

Our solution was an activity we’ve taken to calling “labeling parties.”  Every developer at Stack Exchange was asked to go and categorize several randomly chosen users based on their Stack Overflow Careers profile, and we used this to build a data set.  For the developer-kinds problem, our labeling party hand classified 1,237 people.

The Classifier

In our experience, naïvely rubbing standard machine learning algorithms against our data rarely works.  The same goes for developer-kinds.  We attacked this problem in three different steps: structure, features, algorithms.

Looking over the different developer-kinds, it’s readily apparent that there’s an implicit hierarchy.  Many kinds are some flavor of “web developer,” while others are “mobile developer,” and the remainder are fairly niche; we’ve taken to calling “web,” “mobile,” and “other” major developer-kinds.  This observation led us to first classify the major developer-kind, and then proceed to the final labels.

Since we only really have question tag view data to use in the initial version of Providence, all of our features are naturally tag focused.  The breakdowns of the groups of tags used in each classifier are:

• Major Developer-Kinds
  • Web programming languages (java, c#, javascript, php, etc.)
  • Mobile programming languages (java, objective-c, etc.)
  • Non-web, non-mobile programming languages
  • iDevices
  • Web technologies (html, css, etc.)
• Mobile Developer-Kinds
  • iDevice related (ios, objective-c, etc.)
  • Android related (android, listview, etc.)
  • Windows Phone related (window-phone, etc.)
• Other Developer-Kinds
  • Each of the top 100 used tags on Stack Overflow
  • Pairs of each of the top 100 used tags on Stack Overflow
  • SQL related (sql, tsql, etc.)
  • Database related (mysql, postgressql, etc.)
  • Linux/Unix related (shell, bash, etc.)
  • Math related (matlab, numpy, etc.)

For many features, rather than use the total tag views, we calculate an average and then use the deviation from that.  With some features, we calculate this deviation for each developer-kind in the training set; for example, we calculate deviation from average web programming language tag views for each of the web, mobile, and other developer-kinds in the Major Developer Predictor.

Turning these features into final predictions requires an actual machine learning algorithm, but in my opinion, this is the least interesting bit of Providence.  For these predictors we found that support vector machines, with a variety of kernels, produce acceptably accurate predictions; however, the choice of algorithm mattered little, various flavors of neural networks performed reasonably well, and the largest gains always came from introducing new features.

So how well did this classifier perform?  Performance was determined with a split test of job listing ads with the control group being served with our existing algorithm which only considered geography, we’ll be covering our testing methodology in more depth in a future post.  In the end we saw an improvement for 10-30% over the control algorithm, with the largest gains being seen in the Mobile Developer-Kinds and the smallest in the Web Developer-Kinds.

Next up: What technologies do you know?

Your Future On Stack Overflow

I recently spent a while working on a pretty fun problem over at Stack Exchange: predicting what tags you’re going to be active answering in.

Confirmed some suspicions, learned some lessons, got about a 10% improvement on answer posting from the homepage  (which I’m choosing to interpret as better surfacing of unanswered questions).

Good times.

Why do we care?

Stack Overflow has had the curious problem of being way too popular for a while now.  So many new questions are asked, new answers posted, and old posts updated that the old “what’s active” homepage would cover maybe the last 10 minutes.  We addressed this years ago by replacing the homepage with the interesting tab, which gives everyone a customized view of stuff to answer.

The interesting algorithm (while kind of magic) has worked pretty well, but the bit where we take your top tags has always seemed a bit sub-par.  Intuitively we know that not all tags are equal in volume or scoring potential, and we also know that activity in one tag isn’t really indicative just in that tag.

What we’d really like in there is your future, what you’re going to want to answer rather than what you already have.  They’re related, certainly, but not identical.

Stated more formally: what we wanted was an algorithm that when given a user and their activity on Stack Overflow to date, predicted for each tag what percentage of their future answers would be on questions in that tag.  “Percentage” is a tad mislead since each question on Stack Overflow can have up to five tags, so the percentages don’t sum to anything meaningful.

The immediate use of such an algorithm would be improving the homepage, making the questions shown to you more tailored to your interests and expertise.  With any luck the insights in such an algorithm would let us do similar tailoring elsewhere.

To TL;DR, you can check out what my system thinks it knows about you by going to /users/tag-future/current on any of the older Stack Exchange sites.  The rest of this post is about how I built it, and what I learned doing it.

Unsurprisingly, that’s a pretty good model of how I think about my Stack Overflow participation.

What Do We Know?

A big part of any modeling process is going to be choosing what data to look at.  Cast too wide a net and your iteration time explodes, too narrow and you risk missing some easy gains.  Practicality is also a factor, as data you technically have but never intended to query en masse may lead you to build something you can’t deploy.

What I ended up using is simply the answers on a site (their text, creation dates, and so on), along with the tags the associated questions had when the answer was posted.  This data set has the advantage of being eminently available, after all Stack Exchange has literally been built for the purpose of serving answers, and public knowledge.

At various times I did try using data from the questions themselves and an answerers history of asking, but to no avail.  I’m sure there’s more data we could pull in, and probably will over time; though I intend to focus on our public data.  In part this is because it’s easier to explain and consume the public data but also because intuitively answerers are making decisions based on what they can see, so it makes sense to focus there first.

Except with about 315,000 different parts.

A Model Of A Stack Exchange

The actual process of deriving a model was throwing a lot of assumptions about how Stack Overflow (and other Stack Exchanges) work against the wall, and seeing what actually matched reality.  Painstaking, time consuming, iteration.  The resulting model does work (confirmed by split testing against the then current homepage), and backs up with data a lot of things we only knew intuitively.

Some Tags Don’t Matter

It stands to reason that a tag that only occurs once on Stack Overflow is meaningless, and twice is probably just as meaningless.  Which begs the question, when, exactly does a tag start to matter?  Turns out, before about forty uses a tag on Stack Overflow has no predictive ability; so all these tags aren’t really worth looking at in isolation.

Similarly a single answer isn’t likely to tell us much about a user, what I’d expect is a habit of answering within a tag to be significant.  How many answers before it matters?  Looks like about three.  My two answers in “windows-desktop-gadgets” say about as much about me as my astrological sign (Pisces if you’re curious).

Pictured: the state of programming Q&A before Stack Overflow.

Most People Are Average (That’s Why It’s An Average)

What’s being asked on Stack Overflow is a pretty good indicator of what’s being used in the greater programming world, so it stands to reason that a lot of people’s future answering behavior is going to look like the “average user’s” answering behavior.  In fact, I found that the best naive algorithm for predicting a user’s future was taking the site average and then overlaying their personal activity.

Surprisingly, despite the seemingly breakneck speed of change in software, looking at recent history when calculating the site average is a much worse predictor than considering all-time.  Likewise when looking at user history, even for very highly active users, recent activity is a worse predictor than all time.

One interpretation of those results, which I have no additional evidence for, is that you don’t really get worse at things over time you mostly just learn new things.  That would gel with recent observations about older developers being more skilled than younger ones.

You Transition Into A Tag

As I mentioned above, our best baseline algorithm was predicting the average tags of the site and then plugging in a user’s actual observed history.  An obvious problem with that is that posting a single answer in say “java.util.date” could get us predicting 10% of your future answers will be in “java.util.date” even though you’ll probably never want to touch that again.

So again I expected there to be some number of uses of a tag after which your history in it is a better predictor than “site average”.  On Stack Overflow, it takes about nine answers before you’re properly “in” the tag.  Of course there needs to be a transition between “site average” and “your average” between three and nine answers, and I found a linear one works pretty well.

We All Kind Of Look The Same

Intuitively we know there are certain “classes” of users on Stack Overflow, but exactly what those classes are is debatable. Tech stack, FOSS vs MS vs Apple vs Google?  Skill level, Junior vs Senior?  Hobbyist vs Professional?  Front-end vs Back-end vs DB?  And on and on.

Instead of trying to guess those lines in the sand, I went with a different intuition which was “users who start off similarly will end up similarly”.  So I clustered users based on some N initial answers, then use what I knew about existing users to make predictions for new users who fall into the cluster.

Turns out you can cut Stack Overflow users into about 440 groups based on about 60 initial tags (or about 30 answers equivalently) using some really naive assumptions about minimum distances in euclidean space.  Eyeballing the clusters, it’s (very approximately) Tech stack + front/back-end that divides users most cleanly.

We’d also expect chocolate in there.

One Tag Implies Another

Spend anytime answering on Stack Overflow and you’ll notice certain tags tend to go together.  Web techs are really good for this like “html” and “css” and “javascript” and “jquery”, but you see it in things like “ios” and “objective-c”.  It stands to reason that answering a few “c#” questions should raise our confidence that you’re going to answer some “linq-to-object” questions then.

Testing that assumption I find that it does, in fact, match reality.  The best approach I found was predicting activity in a tag given activity in commonly co-occurring tags (via a variation on principal component analysis) and making small up or down tweaks to the baseline prediction accordingly.  This approach depends on there being enough data for co-occurrence to be meaningful, which I found to be true for about 12,000 tags on Stack Overflow.

Trust Your Instincts

Using the Force is optional.

One pretty painful lesson I learned doing all this is: don’t put your faith in standard machine learning.  It’s very easy to get the impression online (or in survey courses) that rubbing a neural net or a decision forest against your data is guaranteed to produce improvements.  Perhaps this is true if you’ve done nothing “by hand” to attack the problem or if your problem is perfectly suited to off the shelf algorithms, but what I found over and over again is that the truthiness of my gut (and that of my co-workers) beats the one-size-fits-all solutions.  You know rather a lot about your domain, it makes sense to exploit that expertise.

However you also have to realize your instincts aren’t perfect, and be willing to have the data invalidate your gut.  As an example, I spent about a week trying to find a way to roll title words into the predictor to no avail.  TF-IDF, naive co-occurrence, some neural network approaches, and even our home grown tag suggester never quite did well enough; titles were just too noisy with the tools at my disposal.

Get to testing live as fast as you possibly can, you can’t have any real confidence in your model until it’s actually running against live data.  By necessity much evaluation has to be done offline, especially if you’ve got a whole bunch of gut checks to make, but once you think you’ve got a winner start testing.  The biggest gotcha revealed when my predictor went live is that the way I selected training data made for a really bad predictor for low activity users, effectively shifting everything to the right.  I solved this by training two separate predictors (one for low activity, and one for high).

Finally, as always solving the hard part is 90% of the work, solving the easy part is also 90% of the work.  If you’re coming at a problem indirectly like we were, looking to increase answer rates by improving tag predictions, don’t have a ton of faith in your assumptions about the ease of integration.  It turned out that simply replacing observed history with a better prediction in our homepage algorithm broke some of the magic, and it took about twenty attempts to realize gains in spite of the predictor doing what we’d intended.  The winning approach was considering how unusual a user is when compared to their peers, rather than considering them in isolation.

Again, want to see what we think you’ll be active in?  Hit /users/tag-future/current on your Stack Exchange of choice.

Kids These Days

I freely admit about 1/2 the following content is just an excuse to use this title.

Lately I’ve found myself wondering, how are kids getting into programming these days?  I blame still attending the Stack Exchange “beer bashes” (though I think Github’s “drinkups” have won the naming battle there), while no longer being able to drink for these thoughts.  Programmers like to talk about programming, and drunks like to talk about the past, so drunk programmers… well you see where I’m going with this.  Anyway, it seems like the high level stuff has become more accessible, while the “what is actually happening”-bits are increasingly hidden.

Let Me Explain That Last Bit

Every kid who has touched a computer since 2001 has had access to decent javascript, and the mountains of examples view-source entails.  Today Java, C#, Python, Ruby, etc. are all freely available along with plenty of tutorials and example code.  That’s a hell of a lot more than what was out there when I started, but it’s all a few dozen levels of abstraction up.  And that’s my concern, the bare metal is really deep down and stumbling upon it is quite hard.

When I Was Your Age…

I first starting coding on a TI-99/4A, in TI-BASIC, at the age of 5. That’s a machine you can fit in your head.  The processor spec is ~40 pages long (the errata for the Core 2 Duo is almost 100 pages), and there’s none of the modern magic, like pipe-lining, branch prediction, or pre-fetching (there’s not even an on chip cache!).

Now of course, I didn’t actually understand the whole machine at 5 but the people teaching me did.  Heck, the only reason a machine discontinued in ’84 was available to me in ’92 was because they’d worked on the thing and saved a couple.

A grounding in such a simple machine lead me to question a lot about the higher level languages I eventually learned.  For example when I first started learning Java the idea that two functions with the same name could exist just messed with my head, because it didn’t gel with my previous experience, driving me to read up on namespacing and vtables.

Never did figure out how to catch Mew though.

Looking back, another avenue for programming knowledge is how horribly glitchy video games were.  Actually, video games are still horribly glitchy but the consoles are a lot more sophisticated now.  Used to be when a game went sideways the consoles just did not care, and you could do all wreak all sorts of havoc exploiting glitches.  I can honestly say I “got” pointers/indirection (though I don’t remember if I knew the words or not) when I wrapped my head around the infamous Cinnibar Island glitch.  Some of these style glitches can still happen on modern consoles, but there’s proper memory protection and some spare cycles to spend on validation now so they’re a lot rarer.

If you shift my story forward to the present day, a kid learning on 8 year old hardware would be using a PC running Windows XP (probably with a Pentium 4 in it); a simple machine that is not.  Their consoles have hypervisors, proper operating systems, and patches!  If you play Pokémon today you actually only have one masterball.  The most archaic kit they’re likely to encounter is a TI-83 calculator (which still has a Z80 in it), and even then not till high school.

Lies To Children

Which has some serious issues on the Surface RT; fix is pending approval in the app store.

Thinking about this lead me to write Code Warriors, a dinky little coding puzzle app, as my “see if XAML sucks any less than it used to” side project (the answer is yes, but the REPL is still bad).  Even it’s a lies to children version of assembly, making significant compromises in the name of “fun”.  And while I was thinking about kids learning, I certainly didn’t play test it with any children so… yeah, probably not great for kids.

I have no doubts we’re going to keep producing great programmers.  Colleges, the demands of the job market, and random people on the internet will produce employable ones at least.  But I find myself wondering if we aren’t growing past the point where you can slip into programming as if by accident.  It is after all quite a young field, kids in college when ENIAC was completed are still alive, so perhaps it’s just a natural progression.

Trustable Online Community Elections

Keeping votes secure for a couple thousand years, and counting.

One of the hallmarks of successful online communities is self-governance, typically by having some or all admins/moderators/what-have-yous come from “within” the community.  Many communities select such users through a formal election process.  Wikipedia and Stack Exchange (naturally) are two large examples, you’ve probably stumbled across a number of forums with similar conventions.

But this is the internet, anonymity, sock-puppetry, and paranoia run wild.

How can we prove online elections are on the up-and-up?

First, a disclaimer.  Today the solution is always some variation of reputation; sock puppetry is mitigated by the difficulty inherent in creating many “trusted” users, and the talliers are assumed to be acting in good faith (they, after all, are rarely anonymous and stand to lose a lot if caught).  This works pretty well, the status quo is good; what I’m going to discuss is interesting (I hope), but hardly a pressingly needed change.

Also, this is just me thinking aloud; this doesn’t reflect any planned changes over at Stack Exchange.

Modeling the threat

We need to define what we’re actually worried about (so we can proof our solution against it), and what we explicitly don’t care about.

Legitimate concerns:

• Ballot box stuffing
• Vote tampering
• Vote miscounting

Explicitly ignoring:

• Voter impersonation
• Voter intimidation

The concerns are self explanatory, we just want to make sure only people who should vote do vote, that their votes are recorded correctly, and ultimately tallied correctly.

Attacks which we’re explicitly ignoring require a bit more explanation.  They all ultimately descend from the fact that these elections are occurring online, where identity is weak and the stakes are relatively low.

It is hard to prove who’s on the other end of the internet.

Consider how difficult it is to prove Jimmy Wales is actually tweeting from that account, or the one actually editing a Wikipedia article.  Since identity is so much weaker, we’re assuming whatever authentication a community is using for non-election tasks is adequate for elections.

We discount voter intimidation because, for practically all online communities, it’s impractical and unprofitable.  If you were to choose two Stack Overflow users at random, it’s 50/50 whether they’re even on the same side of the Atlantic much less within “driving to their home with a lead pipe”-distance.  Furthermore, the positions being run for aren’t of the high-paying variety.  Essentially, the risk and difficulty grossly outweigh the rewards so I feel confident in discounting the threat.

The Scheme

Before we get too deep into the technical details, I need to credit VoteBox (Sandler, Wallach) for quite a lot of these ideas.

Voter Rolls

To protect against ballot stuffing, it’s important to have a codified list of who can participate in a given election.  This is a really basic idea, you have to register to vote (directly or otherwise) in practically all jurisdictions.  But in the world of software it’s awfully tempting to do a quick “User.CanVote()” check at time of ballot casting, which makes it impossible to detect ballot box stuffing without consulting a historical record of everything that affects eligibility (which itself is almost impossible to guarantee hasn’t been tampered with).

Therefore, prior to an election all eligible voters should be published (for verification).  Once the election starts, this list must remain unchanged.

It’s A Challenge

Vote tampering (by the software typically) is difficult to proof against, but there are some good techniques.  First, all ballots must actually be stored as ballots; you can’t just “Canididate++” in code somewhere, normalized values in a database are no good to anyone; you need the full history for audits.  Again, this is common sense in real world elections but needs to be explicit for online ones.

This does make voting a little more confusing.

A more sophisticated approach is to make individual ballots “challenge-able”.  The idea is simple: break up “casting a ballot” into two parts, “stage” and “commit/challenge”.  When a ballot is staged, you publish it somewhere public (this implies some cryptography magic, which we’ll get back to later).  If the voter then “commits” their vote you make a note of that (again publicly), but if they “challenge” it you reveal the contents of the ballot (this implicitly spoils the ballot, and some more crypto-magic) for verification.  Obviously, if what the voter entered doesn’t match what the ballot contained something is amiss.

Challenge-able ballots make it possible for a group of voters to keep the system honest, as there’s no way for the system to know who will challenge a ballot any vote tampering carries a risk of being discovered. And with the internet being the internet news will get around quickly that something is up once tampered with ballots are being found, making the odds of challenging greater.

Freedom From Hash Chains

For challenges to work there needs to be a method for publishing “committed” ballots.  We could use something low-tech like an RSS feed, mailing list, or similar but ideally we’d have some guarantee that the feed itself isn’t being tampered with.  Consider the attack where some unchallenged ballots are removed from the feed long after they were published, or new ones are added as if they were cast in the past.

Our go-to solution for that is pushing each ballot (as well as some “keep alive” messages, for security reasons) into a modified hash chain.  The idea is simple, every new message contains a hash of the message before it.  Verifying no illicit insertions or deletions is just a matter of rehashing the chain one piece at a time and making sure everything matches.  You can also take a single message and verifying that it still belongs in the chain at a later date, meaning that people who want to verify the chain don’t have to capture every message the instant it’s published.

Note that the VoteBox system goes a step further and creates a “hash mesh” wherein multiple voting machines hash each others messages, to detect tampering done from a single machine.  In our model, all the machines are under the direct control of single entity and voters lack physical access to the hardware; the additional security of a “hash mesh” isn’t really present under this model accordingly.

Time Is Not On Your Side

One subtle attack on this hash chaining scheme: if you’re sufficiently motivated you can pre-compute them.  While far from a sure thing, with sufficient analytic data to predict about when users will vote, how likely they are to vote, challenge, and so on you could run a large number of fake elections “offline” and then try and get away with publishing one that deviates the least (in terms of time and challenged ballots) from reality.  With the same information and considerably more resources you could calculate fake elections on the fly starting from the currently accepted reality and try and steer things that way.  Since the entities involved typically have lots of computing resources, and elastic computing being widely available, we have to mitigate this, admittedly unlikely, but not impossible attack.

The problem in both cases is time.  An attacker has a lot of it before an election (when the voter roll may not be known, but can probably be guessed) and a fair amount of it during one.

Any independent and verifiable random source will do.

We can completely eliminate the time before an election by using a random root message in the hash chain.  Naturally we can’t trust the system to give us a randomly generated number, but if they commit to using something public and uncontrollable as the root message then all’s well.  An example would be to use the front page headline of some national newspapers (say the New York Times, USA Today, and the Wall Street Journal; in that order) from the day the election starts as the root message.  Since the root block is essentially impossible to know, faking a hash chain is no longer easier given the aforementioned analytic data.

To make attacking the hash chain during the election difficult we could introduce a random source for keep-alive payloads, like twitter messages from a Beiber search.  More important would be selecting a hash function that is both memory and time hard, such as scrypt.  Either is probably sufficient, but scrypt (or similar) would be preferable to Beiber if you had to choose.

Tallying Bananas

Thus far we’ve mostly concerned ourselves with individual ballots being tampered with, but what about the final results?  With what’s been discussed thus far, it’s still entirely possible that everyone votes, challenges, and audits to their hearts’ content and at the end of the election totally bogus results are announced.

The problem is that the ballots that count are necessarily opaque (they have to be encrypted clearly, even if we are publishing them), only the challenged ones have been revealed.

There do exist encryption schemes that can work around this.  Namely, any homomorphically additive encryption function; in other words, any encryption function E(x) for which there exist a function F(x1, x2) such that F(E(a), E(b)) = E(a+b).  Two such schemes are (a modified) ElGamal and Paillier (others exists), the ephemeral keys present in ElGamal are useful for our ballot challenge scheme.

Encrypting ballots with ElGamal and publishing them allows anyone to tally the results of the election.  The only constraint imposed by this system is that the voting system being used must be amenable to its ballots being represented by tuples of 1s and 0s; not a big hurdle, but something to be aware of.

This attack is like ballot stuffing with a single very large ballot.

Another subtle attack, since ballots are opaque nothing prevents a ballot from containing something other than 0 or 1 for a slot in a “race” (or all 1s, or any other invalid combination).  Some more crypto-magic in the form of zero knowledge proofs (specifically non-interactive ones) attached to a ballot for every “race” it contains gives us confidence (technically not 100%, but we can get arbitrarily close to it) that every ballot is well-formed.  The exact construction is complicated (and a bit beyond me, honestly), but the Adder system [Kiayias, Korman, Walluck] has provided a reference implementation for ElGamal (adapted into VoteBox, the Adder source seems to have disappeared).

There’s one last elephant in the room with this system.  Although everyone can tally the votes, and everyone can verify each individual vote is well-formed, those running the election are still the only ones who can decrypt the final results (they’re the only ones who have the ElGamal private key).  There honestly isn’t a fool-proof solution to this that I’m aware of, as revealing the private key allows for individual ballots to be decrypted in addition to the tally.  Depending on community this may be acceptable (ie. ballot privacy may only matter during the election), but that is more than likely not the case.  If there is a trusted third party, having them hold in the key in escrow for the duration of the election and then verify and decrypt the tally.  In the absence of a single third-party, a threshold scheme for revealing the private key may be acceptable.

Altogether Now

In short, the proposed system works like so:

• Prior to the election starting, a full roll of eligible voters is published
• When the election starts, a hash chain is started with an agreed upon (but random) first message
  • The hash chain uses a memory and time hard hash function
• A public/private key pair for a homomorphically additive encryption system is stored in an agreed upon manner
• Optionally, throughout the election agreed upon (but random) messages are added to the hash chain as keep-alives

When a user votes:

• Their selections are encrypted using the previously generated public key
• A NIZK is attached to the ballot to prove its well-formedness
• An identifying token is also attached to the ballot to check against the voter roll
• All this data is pushed to the hash chain as a single message
• The voter then chooses to either commit or challenge their ballot
  • If they commit, a message is added to the hash chain to this effect
  • If they challenge, the ephemeral key for the ballot is published; allowing any third-party to decrypt the ballot, letting the voter prove the election is being run in good faith (they may then cast another ballot)

When the election ends:

• Some pre-agreed upon message is placed in the hash chain
  • It’s not important this message be random, it’s just a signal that those watching can stop as the chain is finished
• Anyone who wishes to can verify the integrity of the published hash chain, along with the integrity of individual ballots
• Anyone who wishes to may tally the votes by exploiting the homomorphic properties of the chosen encryption scheme
• Whichever approach to decrypting the tally has been chosen is undertaken, concluding the election

Improvements

The obvious place to focus on improving is the final decryption.  My gut (with all the weight of a Bachelor’s in Computer Science, so not a lot of weight) tells me there should be a way to construct a proof that the announced tally actually comes from decrypting the summed ciphertexts.  Or perhaps there’s some way to exploit the one-to-many nature of ElGamal encryption to provide (in advance of the election naturally) a function that will transform the tally ciphertext into one a different key can decrypt, but have that transformation not function on the individual ballots.

Of course, as I stated before, the status quo is acceptable.  It’s just fun to think of what we could build to deal with the theoretical problems.

Are you measuring your social media buttons?

I’d like you to go to a Stack Overflow (or any Stack Exchange) question, and see if you spot a nominally major change.  Such as this one, with a nice answer from Raymond Chen (I think it’s been more than month since I recommended his blog, seriously go read it).

Spot it?

Of course not, what we did is remove our social media sharing buttons.

Left is old, right is new.  A number of other instances were also removed.

The Process

I’m a big advocate of arguing from data and while I freely admit there are many things that are hard to quantify, your gains from social media buttons aren’t one of them.

When discussing sharing buttons, be careful about establishing scope.  Keeping or removing social media buttons isn’t about privacy, personal feelings on Twitter/Facebook/G+, or “what every other site does” (an argument I am particularly annoyed by); it’s about referred traffic and people.  There’s a strong temptation to wander into debate, feeling, and anecdotal territory; stick to the data.

You also need to gather lots of data, at Stack Exchange we prefer to slap a pointless query parameter onto urls we’re tracking.  It’s low tech, transparent, and doesn’t have any of the user facing penalties redirects have.  In particular we slapped ?sfb=1, ?stw=1, and ?sgp=1 onto links shared via the appropriate sharing buttons.  Determining click-throughs is just a matter of querying traffic logs with this approach.  We’ve been gathering data on social media buttons in particular for about four months.

Note that we’re implicitly saying that links that are shared that nobody clicks don’t count.  I don’t think this is contentious, spamming friends and followers (and circlers(?), whatever the G+ equivalent is) is a bit on the evil side. Somebody has to vindicate a share by clicking on it, otherwise we call it a waste.

This sort of nonsense isn’t worth it.

With all this preparation we can actually ask some interesting questions; for Stack Exchange we’re interested in how much traffic is coming from social media (this is an easy one), and how many sharers do so through a button.

Traffic gave us no surprises, we get almost nothing from social media.  Part of this is probably domain specific, my friends really don’t care about my knowledge of the Windows Registry or the Diablo III Auction House.  The sheer quantity of traffic coming from Google also drowns out any other source, it’s hard to get excited about tweaking social media buttons to bring in a few thousand extra views when tiny SEO changes can sling around hundreds of thousands.  To put the difference in scale in perspective, Google Search sends 3 orders of magnitude more traffic our way then the next highest referrer which itself sends more than twice what Twitter does (and Twitter is the highest “social” referrer).

Now that I’ve established a (rather underwhelming) upper-bound for how much our share buttons were getting us, I need to look at what portion can be ascribed to the share buttons versus people just copy/pasting.  This is where the slugs come in, presumably no-one is going to add a random query parameter to urls they’re copy/pasting after all.

You basically want to run a query like this:

SELECT *
FROM TrafficLogs
WHERE
-- everybody tries to set Referer so you know you got some juice from them
(RefererHost = 't.co' OR RefererHost = 'plus.url.google.com' OR RefererHost = 'www.facebook.com')
AND
-- Everybody scrapes links that are shared, don't count those they aren't people
UserAgent NOT LIKE '%bot%'
AND
-- Just the share buttons, ma'am
(Query LIKE '%stw=1%' OR Query LIKE '%sfb=1%' OR Query LIKE '%sgp=1%')

Adapt to your own data store, constrain by appropriate dates, etc. etc.  But you get the idea.  Exclude the final OR clause and the same query gives you all social media referred traffic to compare against.

What we found is that about 90% of everyone who does share, does so by copy/pasting.  Less than 10% of users make use of the share buttons even if they’ve already set out to share.  Such a low percentage of an already pretty inconsequential number doesn’t bode well for these buttons.

One final bit of investigation that’s a bit particular to Stack Exchange is figuring out the odds of a user sharing their newly created post.  We did this because while we always show the question sharing links to everyone, the answer sharing links are only shown to their owner and only for a short time after creation.  Same data, a little more complicated queries, and the answer comes out to ~0.4%.  Four out of every thousand new posts* on Stack Overflow get shared via a social media button (the ratio seems to hold constant for the rest of Stack Exchange, but there’s a lot less data to work with so my confidence is lower on them).

Data Shows They’re No Good, Now What?

Change for change’s sake is bad, right?  Benign things shouldn’t be moved around just because, but for social media buttons…

We know our users don’t like them, they’re sleezy (though we were very careful to avoid any of the tracking gotchas of +1 or Likes), and they’re cluttering some of our most important controls (six controls in a column on every question is a bit much, but to be effective [in theory] these buttons have to be prominent).

These buttons start with a lot of downsides, and the data shows that for us they don’t have much in the way of upsides.  So we we could either trudge along telling ourselves “viral marketing” and “new media” (plus we’ve already got them right, why throw them away?), or admit that these buttons aren’t cutting it and remove them.

So, are you measuring the impact of your site’s social media buttons?

You’re probably not in the same space as Stack Exchange, your users may behave differently, but you might be surprised at what you find out when you crunch the numbers.

_{*By coincidence this number seems to be about the same for questions and answers, it looks like more people seeing question share buttons balances out people being less enthusiastic about questions.}