Re: Challenge: A malicious election

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];
}
[download]

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

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 Voter Motor\n";
print "Your candidates are:\n";
print map { "$_\n" } sort @valid_candidates;
print "Enter one name per line, end with EOF.\n";

while ( my $candid_date = lc <> ) {
    chomp $candid_date;

    if ( exists $tally_for{ $candid_date } ) {
        $tally_for{ $candid_date }++;
    }
    else {
        warn "Write-in for $candid_date\n";
        $tally_for{ $candid_date }++;
    }
}

my @winner_first = reverse
                   sort { $tally_for{$a} <=> $tally_for{$b} }
                   keys %tally_for;
foreach my $who ( @winner_first ) {
    printf "%10s : %d\n", $who, $tally_for{$who};
}
[download]

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":

Keeping tallies as single element array references is a distraction. I thought I might write a bug based on using the wrong array reference, but I never did.

The bug is in the validation loop. Because $candidate is set to a valid candidate on each iteration, it will be left with the last candidate's name if the user's input doesn't match any name. As such, the write-in branch is never reached, and all write-in or typo votes go to Eve.

An earlier version left out the chomp so every vote went to Eve (because the dangling newline would thwart matching every candidate). I thought that was a more subtle bug, but it makes the election results too obviously wrong.

Comment on Re: Challenge: A malicious election Select or Download Code

Replies are listed 'Best First'.
Re^2: Challenge: A malicious election by blokhead (Monsignor) on Jun 12, 2008 at 17:04 UTC
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; [download] 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	[reply] [d/l] [select]
Re^2: Challenge: A malicious election by Porculus (Hermit) on Jun 13, 2008 at 22:46 UTC
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...	[reply]


Perl: the Markov chain saw
	PerlMonks