Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Challenge: A malicious election

by blokhead (Monsignor)
on Jun 11, 2008 at 21:38 UTC ( #691549=perlmeditation: print w/ replies, xml ) Need Help??

I want you to write malicious election software in Perl!

Rules:

Your program should:
  1. Present a list of candidates (feel free to fill the ballot with whatever names you like) and instructions on how to enter votes.
  2. Read votes from STDIN, according to the instructions.
  3. After voting is finished (by entering a special command, or closing STDIN), display the final vote count for each candidate.
You should strive for the following virtues of malicious election software:
Covertness

The program's source code should look completely benign. In other words, it should appear to correctly count the given votes, according to the instructions printed out, and not appear to do anything else suspicious. It should not appear intentionally obfuscated. You want this code to pass a source inspection and get included in election equipment.*

Likewise, the results of the election should be plausible. If all votes go to one candidate, or the number of votes is vastly different than what was entered, people will get suspicious!

Deviousness / Ingenuity

When executed, the program should definitely not be benign, but instead rig the election! Be creative in how you tamper with the election. Some example ideas:

  • Steal occasional votes from one candidate and give them to your preferred candidate
  • Always ensure that your favorite candidate wins by a slight margin
  • Always force a tie
  • Elect yourself as a write-in candidate
  • Include a backdoor triggered by malformed input
  • Randomly assign votes to candidates, ignoring all actual submitted votes.

It should be quite a challenge to achieve both of these virtues simultaneously. In essence, this is an obfuscation challenge, but only the malicious intent should be obfuscated; the rest of the code should look unobfuscated.

Some other devious ideas:

  • Count votes correctly when tested, except when the code is run on the day of the election (November 4 in the USA)
  • Include (apparent) integrity checks on the voting data, while still tampering with the election

Misc:

This was inspired by this obfuscation contest. You might be inspired by some of the submissions. Some of the top submissions were very good, and it's hard to see where the votes are getting screwed up, even if you know the code has a hole somewhere. That contest used C, but of course, I encourage clever ideas that are unique to Perl.

If you feel like including them, put hints and post-mortem analyses in <spoiler> tags.

Sample code:

Here is a sample program that counts votes correctly -- of course, yours shouldn't:
use strict; use warnings; my %ballot = qw( Obama 0 McCain 0 Barr 0 blokhead 0); print "Available candidates: @{[ keys %ballot ]}\n"; print "To cast a vote, type candidate's full name. End the election wi +th ^D\n"; while (<>) { chomp( my $vote = $_ ); if ( exists $ballot{$vote} ) { $ballot{$vote}++; } else { warn "Invalid candidate!\n"; } } print "Final results:\n"; printf "%10s : %d\n", $_, $ballot{$_} for sort { $ballot{$b} <=> $ballot{$a} } keys %ballot;
Feel free to deviate from my sample code in how you store the votes, expect the votes to be given in STDIN, display the results, etc..

*: You'll have to use your imagination and pretend that voting machine companies actually review their code.

blokhead

Comment on Challenge: A malicious election
Download Code
Re: Challenge: A malicious election
by Erez (Curate) on Jun 12, 2008 at 06:45 UTC
Re: Challenge: A malicious election
by ambrus (Abbot) on Jun 12, 2008 at 08:53 UTC
Re: Challenge: A malicious election
by kyle (Abbot) on Jun 12, 2008 at 15:12 UTC

    Here's my feeble entry:

    use strict; use warnings; my @valid_candidates = ( 'Alice', 'Bob', 'Charlotte', 'David', 'Eve' ) +; my %tally_for = map { lc($_) => [0] } @valid_candidates; print "Welcome to the Die Bold 691549 Electrified Election Estimator\n +"; print "Your candidates are:\n"; print map { "$_\n" } sort @valid_candidates; print "Enter one name per line, end with EOF.\n"; while ( defined( my $candid_date = <> ) ) { chomp $candid_date; my $candidate; foreach ( @valid_candidates ) { last if lc $candid_date eq ( $candidate = lc $_ ); } if ( exists $tally_for{ $candidate } ) { $tally_for{ $candidate }->[0]++; } else { warn "Write-in for $candid_date\n"; $tally_for{ lc $candid_date }->[0]++; } } my @winner_first = reverse sort { $tally_for{$a}->[0] <=> $tally_for{$b}->[0] +} keys %tally_for; foreach my $who ( @winner_first ) { printf "%10s : %d\n", $who, $tally_for{$who}->[0]; }

    What's hard about this is that a correct solution is so simple. Here's one that works:

    Vote counting and reporting take all of 15 lines with no golfing. Practically any deviation from a simple "stash in a hash" implementation is going to be suspicious. I think the best bet for really sneaking something in is to write a lot of bad code that mostly works. Another strategy might be to exploit a bug in some software that the machine uses (e.g., a MySQL bug) rather than have a bug in the machine itself.

    Anyway, it's an interesting "problem" but having skulked about the Monastery for a while, I can't imagine I'd get anything past the monks.

    Update: I should spoiler out an explanation. So, here's what my entry does "wrong":

      Your comment in the spoiler made me think of this kind of an approach to
      exploit the extra level of arrays:
      use strict; use warnings; my @candidates = qw( Alice Bob ); ## initialize each candidate with 0 votes my %votes; @votes{map lc, @candidates} = ( [0] ) x @candidates; print "Available candidates: @candidates\n"; print "To cast a vote, type candidate's name. End the election with ^D +\n"; ## record the input vote while (<>) { chomp( my $vote = lc $_ ); if ( exists $votes{$vote} ) { $votes{$vote}[0]++; } else { warn "Invalid candidate!\n"; } } ## print all votes print "Final results:\n"; printf "%10s : %d\n", $_, $votes{lc $_}[0] for @candidates;
      What it does wrong:
      Every value in %votes is a reference to the same array ref. So all votes are actually recorded for both candidates, and the election is a tie. This isn't ideal in terms of covertness, since the program reports twice as many votes as were cast.

      What would be much nicer is if there is some way to sneak in a division-by-two on the votes, so there will always be the right number of votes (or one less). Perhaps someone can think of a way to sneak  >>=1 in there? Or some cleverness in the printf template?

      I also think that since having the extra array ref in there is suspicious, one could try to store extra data in the array @{ $votes{$candidate} }. I couldn't think of anything very convincing though.

      blokhead

      Vote counting and reporting take all of 15 lines with no golfing. Practically any deviation from a simple "stash in a hash" implementation is going to be suspicious.

      I'd have thought there was plenty of room for legitimate complexity.

      For example, is it really reasonable that a user accidentally typing "Alcie" instead of "Alice" should effectively lose their vote? Of course not! Clearly, to make sure that every vote is correctly recorded, we need much more sophisticated validation routines...

Re: Challenge: A malicious election
by hardburn (Abbot) on Jun 12, 2008 at 17:16 UTC

    Likewise, the results of the election should be plausible. If all votes go to one candidate, or the number of votes is vastly different than what was entered, people will get suspicious!

    The trick here is that there are good statistical ways of measuring what "vastly different" means. In practice, it's only possible to swing the vote by 1-2% within the software as long as election officials are practicing even the smallest amount of due diligence. While that would have been enough to swing the last two US Presidential elections and some congressional elections, it won't work in the general case.


    "There is no shame in being self-taught, only in not trying to learn in the first place." -- Atrus, Myst: The Book of D'ni.

Re: Challenge: A malicious election
by zentara (Archbishop) on Jun 12, 2008 at 17:31 UTC
    Warning: Consult a revolutionary immediately, if you experience an election lasting more than 4 weeks. :-)

    I'm not really a human, but I play one on earth CandyGram for Mongo
Re: Challenge: A malicious election
by samizdat (Vicar) on Jun 16, 2008 at 17:22 UTC
    ROFLVVH... and then crying my eyes out because it's so real. The sad thing is that it isn't even the Diebolds we should fear, or the union riggers who "accidentally" drop voting machines in downtown Philadelphia, but the boxes of uncounted votes that deliberately end up in trash cans and dry arroyos. According to one source, well over three million votes the last time.

    Y'alls will pardon my temerity, but I'm building a company around rectifying this issue once and for all... for real, no foolin', and no stoppin' us.

    More to come in a few weeks. :D

    Don Wilde
    "There's more than one level to any answer."

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://691549]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (8)
As of 2014-08-29 23:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (289 votes), past polls