BBV: An idealistic look at the big picture (techies & non-techies welcome)

[scottxyz]

As an experienced Microsoft Access programmer with background in formal methods of software specification, implementation and verification, I agree that writing a database WITHOUT referential integrity (the way Diebold apparently wrote GEMS) is a big mistake. True professionals NEVER forsake referential integrity when writing a database.

Take a little journey below through the state of the art in software engineering - from Diebold to DARPA - if you need a reminder of just how pathetic current American voting-system software really is.

Referential integrity (RI)
Referential integrity is the "relationship" between a "parent" and a "child" table.

For example: in a typical vendor-invoice tracking system, the INVOICE table would be the child of the VENDOR table. Referential integrity simply reinforces the requirement that there can never be an INVOICE with a blank VENDOR field. Nor can there be an INVOICE with "Smith, John" in the VENDOR field if there is no "Smith, John" record in the VENDOR table.

ALL professional database management systems (except for MySQL) offer declarative referential integrity. Leaving it out is not an "option" or a question of "style" - it is universally recognized as a mistake among all programmers.

(In MySQL, which lacks "declarative" referential integrity, programmers often implement RI "procedurally" - ie, they "roll their own" code to handle this important function.)

"Declarative" just means that the programmer gets referential integrity by simply checking a box somewhere in the design - they don't have to do any coding to get this. That's how easy it is to get referential integrity in Access - the programmer just has to check a box called "Enforce Referential Integrity"!

I HAVE seen many amateur Microsoft Access programmers (typically Excel "power users" who want to try doing a database) who do NOT turn on {declarative} referential integrity in Access. Over time, such programs always have corruption - ie, orphaned child records, such as described above, or near-dupes, as illustrated below.

For example, on a recent assignment to write a vendor-invoice tracking system, when I started they already had a rudimentary Access database written by someone in-house. They had about 30,000 invoices in the system. About 5,000 invoices had a bad vendor in them and couldn't be included in totals. (Roughly a 16% error rate - enough to throw most of our hotly-contested elections.)

For example:

Invoice ID : 11111
Vendor ID : Acme
Amount : $10,000

Invoice ID : 11112
Vendor ID : Acme, Inc.
Amount : $9,000

Invoice ID : 11112
Vendor ID : Acme
Amount : $9,000

Invoice ID : 11113
Vendor ID : Acme Supplies, Inc.
Amount : $8,000

Invoice ID : 99999
Vendor ID : {BLANK}
Amount : $50,000

Invoice ID : 98765
Vendor ID : {BLANK}
Amount : $7,500

Invoice ID : 11114
Vendor ID : Acme Supplies d/b/a NY SYSTEMS
Amount : $7,000

Invoice ID : 11115
Vendor ID : NY SYSTEMS
Amount : $6,000

Invoice ID : 11112
Vendor ID : Acme
Amount : $9,000

Dupes and dropouts
Without referential integrity, there is simply no way to total up all the invoices from Vendor "Acme" (and "Acme, Inc." and "Acme Supplies, Inc." etc.) (Similarly, without referential integrity, there is simply no way to total up all the BALLOTS cast for a particular CANDIDATE. There will inevitably be dupes and dropouts.)

Another thing I hear Diebold doesn't do is implement primary keys or unique indexes. This allows dupes (duplicate records) to be entered. Look at the 3rd and the last invoices above. Same vendor id, same invoice number, same amount. Very likely this is a dupe. The system automatically prevents you from entering dupe records like this if you have a "unique index" on the combination of fields (Vendor ID, Invoice ID). Standard Operating Procedure in Access and all databases - I believe Diebold failed to this in GEMS as well. If this sample database had this primary key defined, the user would be automatically blocked from entering the last record (the dupe).

Then also look at the 2nd invoice above. Same invoice number, similar vendor id, same amount. This is a "near-dupe" which crept in because of the lack of declarative referential integrity. This near-dupe would be prevented by referential integrity and a vendor pick-list on the Invoice screen.

Then look at the 5th invoice. No vendor at all on this one. Going to be pretty hard to add this invoice into the totals. (Declarative referential integrity would block this error.)

I've always viewed my MAIN job as a database programmer to be assuring database integrity - using referential integrity and unique indexes. If you don't do this, you typically end up with anywhere from 5% to 20% of your records corrupted.

The data model or "schema"
When designing a database system, one begins with a "model" or "specification". This is a diagram showing all tables, columns, and the relationships between them.

For example, a simplified specification for the vendor system would be:

create table vendor (
vendor_id text primary key,
vendor_address text,
vendor_city text,
vendor_state text,
vendor_zip text,
vendor_phone text
)

create table invoice (
vendor_id text,
invoice_id text,
invoice_amount number,
invoice_date date,
invoice_paid boolean,
constraint (vendor_id, invoice_id) unique index,
constraint vendor_id references vendor.vendor_id
)

Such a model is commonly developed in a graphical rather than a textual environment, where the programmer just drags the mouse from INVOICE.VENDOR_ID to VENDOR.VENDOR_ID to create the referential integrity. This is exactly how Microsoft Access works.

Two points to emphasize here:

(1) Referential integrity pays off big time, and takes less than a minute to implement. (So WHY doesn't Diebold use it?)

(2) A database system has only ONE correct data model. There are no ifs ands or buts in the data model, no bells or whistles. There may be many "front-ends" - ways of DISPLAYING the data model to the user (one record at a time, all records in a list, different layouts for forms and reports), but for a given database system there is only ONE correct or "canonical" database model or "back-end".

In computer parlance, this database model is called the "schema". It is truly "the" schema - not "a" schema. There is only one schema formalizing a particular specification (or "needs and requirements document"). That's why it's so crucial to get the schema right at the outset. Without it, you're just programming in the dark.

Database specification and implementation
Good programmers spend a lot of time at the beginning of a project going back and forth talking to users to make sure the schema is done right. There is a reason for this: the schema is the formal version of the user "needs and requirements or "specification". (In many programming environments, this database schema is executable without further modification: records can be added, changed, deleted and viewed through some sort of default, out-of-the-box implementation.)

Once the schema or "back-end" is designed, the programmer is free to implement all kinds of bells and whistles in any number of "front-ends" to give the different users different screens and reports for inputting and outputting records.

Although there is only ONE schema or back-end which satisfies a given specification, many different front-ends or implementations can be designed to allow users to add, change, delete and view the records in the underlying back-end. This is why you have to nail the schema first in a database system - it's the easiest and the most important thing there is to nail.

The specification says what the system is supposed to do. An implementation tells the computer how to do it. There are many ways to skin a cat - and there are many ways to do addition. There may be many ways of computing a result (implementations) but they all have to come up with the same, correct answer (satisfy the specification). From this, it's easy to see how crucial it is to develop the specification before attempting an implementation. In databases, the simplest (most compact, "declarative" rather than "procedural" - saying WHAT to do, not HOW to do it) specification is simply the schema. One of the reasons Diebold's voting-system software is so hard to understand is because, by leaving out the schema, they're just giving us an implementation with no specification. It's a big, complicated statement of HOW to do something - while the WHAT that it's supposed to be doing is never explicitly, compactly specified.

One specification, many possible implementations
The point of this is that a database without referential integrity is a database without a schema. And a database without a schema is a database without a formal specification - all it has is an implementation. For a database without a schema (specification), it is nearly impossible to confirm whether a particular implementation satisfies the specification - because there is no formal specification to satisfy!

This, aside from the issue of corrupt records, is one of the most scathing indictments you can make about Diebold's so-called "database systems". There is no formal specification - so there is no way of verifying whether an implementation satisfies a non-existent specification (the user needs and requirements).

A parallel from mathematics
If you remember doing lots of "proofs" of "theorems" (say, in geometry class) you might find this interesting.

One of the most fundamental results discovered in computer science in the 20th century was an "isomorphism" (a structural equivalence) between the following:

- a theorem and its proof

- a specification and its implementation

This is not a mere analogy. This is a mathematical isomorphism - meaning the things involved in a theorem and its proof are EXACTLY THE SAME ("up to renaming") as the things involved in a specification and its implementation. This is a major result! Good programmers who know this result are always sure to write THE formal specification of their system before writing AN implementation which satisfies it.

Of course, a lot of programmers are just into the "secret decoder ring" aspects of the computer "priesthood" and don't care a fig about math, or the fundamental notion of an implementation "satisfying" a specification. They are unable or unwilling to take advantage of this fundamental guiding principle - the isomorphism between theorem/proof and specification/implementation.

(Aside: Bad programmers talk a lot of gobbledygook but good programmers are surprisingly comprehensible. If you can't understand what a programmer is telling you, they're probably programming themselves into corner and/or trying to con you out of your money and/or your data.)

In math class, it would be pretty silly to write a proof without stating up-front the THEOREM that you're attempting to write a proof for.

The exact same thing happens in the computer programming industry: many programmers go around writing IMPLEMENTATIONS without ever stating up-front what the SPECIFICATION of the system is.

In good systems design, after the (largely English) informal "user needs and requirements" document is written up, a more formal specification should be drawn up. In database systems, this specification is the "schema" described above. Its advantages are that many users are able to actively and intelligently participate in developing, critiquing and testing the schema (being more formal than a "needs and requirements" document, it's usually runnable as-is in a rudimentary form - ideal for users who don't know what they really want until they can kick the tires on a "live" system). In well-run, successful software development projects, the specification (the "schema", in the special case of database software development, such as a vote-casting and -tallying system) is quite often treated as a "contract" between programmers and users. It's easy enough for the users to understand, critique and even edit, while it's formal enough for the programmers to simply run it "as is" for rapid-prototyping purposes.

Diebold's voting system, lacking referential integrity and unique indexes (hence lacking a database schema or specification) is a classic example of an implementation in search of a formal specification. Database systems developed without a schema have no "contract" between users and developers. In most cases, such projects simply fail.

An "executable specification" language
For programmers who might be interested in further exploring the relationship between specification and implementation, there is an "executable specification" language called "Maude" funded by DARPA (probably used in a lot of Defense projects, where "provably correct" code is required, and the "debugging" and "patches" prevalent in the less-demanding world of commercial software are not allowed). Maude can be downloaded free at:

http://maude.cs.uiuc.edu/

(It runs best on Linux, but you get get it to run on Windows too.)

The Maude Tutorial and other downloadable manuals are arguably the most important milestone in the history of computer science. While the rest of the world debugs and patches and does testing and QA, the Defense Department specifies programs and proves their correctness. Perhaps most interestingly, this supposedly "advanced" language Maude turns out to be one of the easiest languages for newbies to learn programming with. I have taught several people with no programming experience and very little recollection of math class how to write some simple programs in Maude, such as computing the factorial of X or calculating the number of cannonballs in a pyramid-shaped stack of height Y.

A provably correct vote-casting and -tallying system could be specified in a few pages of Maude code. (I have seen simplified versions of major military applications such as reconnaissance systems written in a few pages. And in Maude nothing is built-in - no libraries, no "DLL Hell". These two-page programs have about a half a page at the start where basic things such as numbers and text-strings are defined.) It is so sad seeing all this squabbling over debugging and testing our country's buggy Microsoft voting software, when the worlds of academia and the military have written policies in place which in effect ban all of Microsoft's (and most other commercial vendors') proprietary, bug-ridden language offerings.

There is an Olympian realm of computer programming where provably correct software is routinely specified and implemented to smoothly handle Herculean tasks such as guiding missiles or solving deep mathematical problems. Meanwhile, in the peanut gallery, the expensive, pointless squabbling and bickering rages on about doing "testing", "commenting", and "quality assurance" with buggy, proprietary, specification-free code which is just supposed to perform secure, private multiple-choice and addition.

Open-source
This discussion of specification and implementations ties in a bit with the whole open-source issue.

There is a great deal of debate about how to best handle issues such as privacy and security in a voting system. These are truly non-trivial programming tasks. Multiple-choice and addition are trivial to program, but privacy and security and verifiability are non-trivial.

If a real effort was being made to do this right, a formal specification handling these aspects would be designed in full public view, using an "executable specification" language such as Maude to model and test the trickier aspects such as privacy, security, auditing and verification. The arguments about "proprietary code" are moot: Perhaps if this were a DARPA weapons system, there might be some point to keeping the specification secret so other governments can't see it. I would however be interested in hearing the arguments why we wouldn't want other governments to be able to get a peek at the specification of a system that supports secure, private and accurate vote-casting and -tallying in accordance with the letter and spirit of our Constitution. If we really want to "make the world safe for democracy", how about putting our code where our mouth is?

[punpirate]

1. It's a nice summation:

"I would however be interested in hearing the arguments why we wouldn't want other governments to be able to get a peek at the specification of a system that supports secure, private and accurate vote-casting and -tallying in accordance with the letter and spirit of our Constitution. If we really want to 'make the world safe for democracy', how about putting our code where our mouth is?"

Ah, because it's not about that. It's about money.... If it weren't, the specifications would already be spelled out in federal law.

We've been much busier making the world safe for American multinational corporations than for democracy.

Cheers.

[BevHarris]

2. Thank you so much for this. It is really a very clear explanation

and shows, in a non-emotional, logical way (typical for scottxyz) what is so disturbing about the GEMS program.

I pulled something out of the source code, it's on my other computer, something to the effect of "parent? parent? anyone want to claim the parent on this? anyone?"

I really appreciate this, scottxyz. Now, check your pm.

Bev

[scottxyz]

3. Not sure what that "parent" might be

(PM'ed you back)

If Diebold didn't use any parent-child relationships in their database schema, then the word "parent" in the source code could of course refer to just about anything. Could just mean "who wants to claim authorship" on a particular line of code.

As a by-product of what was said in the original message here, it's important to remember that it is possible to write a fully functional database nowadays with ZERO source code. It saddens me to see so much effort being expended tearing our hair out trying to understand the source code - when the "meat" of any database system is in the schema (where the data's stored), not the {procedural} source code which just glues all the screens and reports together.

Once you have a database schema, in most languages it's already runnable as-is. Of course, it might not be pretty, and it might lack special screens facilitating special functions (such as handicapped access, etc). But it's a good guideline to bear in mind that {procedural} source code in a database is mostly window-dressing.

A simple (legal) programming policy could stipulate that any systems be made available in this initial, essential form (schema only) for testing and verification. The giant morass of procedural source code (in Visual Basic, as well as compiled, non-human-readable, untestable, potentially malicious modules such as DLLs and OCXs and ActiveX controls) piled onto the (missing) schema in Diebold's software makes it meaningless to try to verify whether the implementation satisifies the specification - because the specification is missing.

Many Microsoft Access programmers get their first version of the database out of the gate by just defining tables, relationships and queries, and then using the Forms Wizard to generate some forms. (Other databases allow you to do this as well.)

This demonstrates a possible guideline, that "in {the first draft of} a well-written database, the amount of {procedural} source code tends toward zero."

[ParanoidPat]

4. Wonderful!

Thank You! I'm soooo glad you're on our side. :evilgrin: :thumbsup:

If we can get a fundraising organization established for a legal defense fund, how much would you charge to be an 'expert' witness? :)

Better yet, would you ever consider a position on the Board of Directors?
Head of the Technical Advisory Board perhaps? LOL!

[Pobeka]

5. Since we're getting philosophical

I checked out maude, briefly.

Yes, it is cool. It is very cool.

But, it's built on top of glibc (or probably the equivalent run-time library on MS).

So, I then think about "Godel, Escher and Bach, The Eternal Golden Braid" by Douglas R. Hoffstadter. (Which I have loaned out, so don't quote me now...)

But there's this ongoing discussion between two characters in that book, about a record player which the first character claims can be destroyed by playing just a record with special characteristics on it.

-To which the second character says, "well, I'll just redesign my record player to check for your special characteristics before it will play the record".

-To which the first character says, "well, I'll make a record that will cause your special characteristics detection system self-destruct when it tries to analyze it".

And so on, and so on.

The first point I'm driving at (bet you were wondering, huh?) is that computers rely on ever increasing complexity in the fundamental building blocks. One of those building blocks is the run-time libraries of the OS. Another is the hardware drivers. Another is the hardware itself. Maude is not going to solve that problem, because maude relies on those fundamental building blocks as well. It's a catch-22. Maude, is analogous to the the record player in Hofstadter's story.

My second point -- Any voting system which comes from a single source, is vulnerable to tampering, because whoever controls that single source, or, whoever can interfer in the delivery system from that single source can permute the system in subtle ways that may not be detectable by election officials.

I have racked my brain (and you may think so too!) for a way to make a computer-based voting using only electronic ballots. And, I can't do it. There are too many weak points in the system that are vulnerable to tampering over too much time.

That's why I support using computers to take the intent of the voter, error check it, and print the final marked ballot. The marked ballot becomes the official ballot, and the computer has nothing else to do with the election. And, I'm also becoming a believer in hand-counting of the ballots. With a computer printing them, they could be designed so they could be cut into individual races, and the voter could drop their vote for a particular race into a separate ballot box, one for each race. It really doesn't take much time to hand-count.

I apologize if this was somewhat obtuse, but it won't have been the first time ;-)

Thanks for another great post scottxyz!

[Pobeka]

7. BTW Philosophical is a GOOD thing

I hope no one (especially scottxyz) thinks I am saying formal specifications and logic aren't useful. They are absolutely critical, and as scottxyz points out, if not done properly (or at all), is the reason many applications finally fail.

[scottxyz]

8. Pobeka - A minor correction re: Maude

You are correct that the freely downloadable version of Maude (which is admittedly an interpreter, not a compiler) does run on top of some existing architectures (such as libraries developed for Linux or Windows).

As you point out, running your verified code on top of some other guy's operating system means there's still a black box somewhere between your program and the chip.

We have no idea what's in Windows as it's a trade secret. On the other hand, we do know what's in Linux. When Linux runs on Intel hardware, I'm not sure if we know what's in the Intel instruction set. (But maybe Andy Grove could be persuaded to tell us, for patriotic reaons.) Or maybe there could be open-source hardware for Linux. Probably not too hard - then you'd be able to verify all the way down to the metal.

What we can't download yet (I imagine this is just for DARPA's use right now) is the Maude COMPILER. Yes, there is one in the works, and I believe it's gone through several releases.

Note that there is NOTHING in Maude at itself all in terms of libraries - the examples are quite beautiful in that whenever you want to use something like numbers of even the Booleans, you have to explicitly define them yourself. In terms of being able to be sure that you know what's going on all the way down from your source code to the hardware, Maude's library-less approach is very promising.

I believe there is a lot of hardware and some operating-system design work going on both supporting and leveraging the general-purpose Maude language. Specifically, I have read proposals for something called a "Rewrite Rule Machine" designed from the ground up to run Maude efficiently. Massively parallel and all that. I don't know if this has been completed. If it were, then there wouldn't be any Linux or Intel or other junk in the middle - it would be all yours, all verifiable, from the source code down to the silicon.

At any rate, Maude in its current form is being successfully used to specify highly-complex hardware AND software systems whose correctness is formally verified by mathematical proofs rather than brute-force (and necessarily incomplete) testing. The notion that "an implementation satisfies a specification" which Maude makes so explicit (essentially by automatically deriving an executable, reasonably efficient implementation from a compact specification, whose correctness can usually be vouched for by mere visual inspection) has been shown to be highly useful for designing systems where many interested parties need to be sure about WHAT the system does.

Picking secure hardware and OSes to run such implementations on, as you pointed out, would be a non-trivial issue not automatically solved just by having an executable specification language such as Maude.

However, WITHOUT a formal specification language letting us compactly specify WHAT a system is supposed to do, the task of picking secure hardware and OSes that faithfully carry out the WHAT might not be just non-trivial, but simply impossible.

[Pobeka]

9. Thanks for the follow up. This is way cool.

You realize of course, I have yet another reason to be engaged in (or distracted by) computer technology? And, it's all your fault. ;-)

[scottxyz]

12. My pleasure Pobeka!

Yes, Maude can be quite distracting! When I ran across Maude several years ago, I embarked on a major detour in my computer studies.

It is unlike anything I've ever seen in programming.

At some point, it was conjectured (I don't know if they proved it yet) that the mathematical logic which Maude is based on, called "rewriting logic", is something called a "logical framework" - ie, a logic in which ANY OTHER logic could be expressed.

If you like programming languages, this one is sort of the "end of the line" - it doesn't get any better than this (except up to renaming!).

[scottxyz]

11. A cure for complexity - algebraic specification languages (eg, Maude)

Pobeka points out: "Computers rely on ever increasing complexity in the fundamental building blocks. One of those building blocks is the run-time libraries of the OS. Another is the hardware drivers. Another is the hardware itself."

This depressing complexity, often referred to as "programming-in-the-large", has been the bane of programming for the last several decades. It was the subject of a NATO conference in the 70s, it was the reason the Denver airport opened several months late (because the baggage-handling system kept screwing up), it causes billions of dollars a year in overruns on programming projects.

Maude, and other algebraic specification languages like it, comes at the end of a long line of languages designed to deal rigorously (mathematically) with just this issue of complexity. Basically, it relies on the following convenient fact: When your (declarative)specifications are actually executable, you get an amazing by-product: formal decomposability and recomposability. Removing all the procedural code makes everything essentially "plug-and-play". You actually get mathematical operators for "gluing" modules together, or for replacing ("reifying") an inefficient specification with its more-efficient implementation. For the first time, the "programming in the large" issue is actually being solved by algebraic specification languages such as Maude. A good overview of this is Ehrig and Mahr's book from Springer Verlag: 'Fundamentals of Algebraic Specification'. (Not for novice programmers!)

Today's large commercial software systems are plagued by problems of plugging lots of little pieces together and testing till the whole thing runs 99.999% of the time. The "object-oriented" movement, by introducing the idea of "encapsulation" (for example, Bertrand Meyer's notion of "programming by contract" introduced in the Eiffel language, as well as public/private/protected methods popularized in C++) went a long way towards fostering "loose coupling" between components, so that when you plugged a bunch of components together you could minimize collisions. But mainly you're just avoiding name collisions, and grouping functions together, and allowing different versions of a function to be called depending on the "type" of its object.

Core Maude goes much further than object-oriented programming. Every module is truly an algebra or a theory in the mathematical sense, rather than an informal collection of (overridable) operators and properties in the o-o sense. Basically, by doing away with ALL procedural code (unlike o-o languages where you still can "be" on a certain line in the code where you're saying "let x=1") and relying exclusively on equational rewriting for both its mathematical and operational semantics, "temporal" or "sequential" or "synchronization" issues vanish, allowing separate modules (whose correctness is easy to verify) to be seamlessly plugged together, and the correctness of the resulting module to be rigorously verified simply by knowing that all the components are correct.

Another major result incorporated into Maude was the resolution of the "inheritance anomaly" which had plagued so many o-o languages before, in a seminal paper by José Meseguer. (Most o-o languages conflate object taxonomy with code reuse - actually two different concepts, with entirely different semantics and requiring separate syntaxes. Java is the only o-o language aside from Maude that I've seen that "got" this as well - with the distinction between "interface" and "class" inheritance.) Any o-o programmer could benefit greatly from reading Meseguer's paper.

Solving the Inheritance Anomaly in Concurrent ObjectOriented Programming (Abstract)
http://citeseer.nj.nec.com/context/26344/0

Interestingly, he took a very Zen-like approach in this paper: he solved a major programming problem by GETTING RID of a bunch of (unnecessary procedural synchronization) code. An excellent case of the KISS principle to keep in mind as we wade through endless pages of Diebold's spaghetti code.

When you take Core Maude and you add on the module composition, importation and parameterization facilities available in Full Maude (kind of like functors in ML), things really start getting heady.

If you enjoy programming, and you hate the mess of "programming in the large", check out some of the documents at the Maude website. It's really a breath of fresh air. I have Core Maude running on my Windows laptop, and it's such a relief to run something where I can look at every tiny module of the program - from the definition of the booleans and the integers all the way up to the "main" program - and confirm that it works. Along with a trusted OS and hardware (which will likely come someday as a result of the verifiable hardware and software design projects being carried out using Maude as a tool) this is going to really raise the bar on how reliable we expect computers to be.

Until then, executable specification languages such as Maude would go a long way towards making explicit (and guaranteeing the correctness of) the design decisions involved in developing large, provably correct software specifications.

Department of Defense policies stipulate that mission-critical systems (such as weapons systems) be written first in a specification language to ensure correctness and verifiablity. If we're going to use software to count our votes, we should also demand that same level of correctness and verifiability that the Pentagon demands.

It is ILLEGAL to use proprietary languages (such as Microsoft's offerings) for mission-critical Defense projects. To comply with the letter and spirit of our Constitution, it should also be ILLEGAL to use proprietary languages for other mission-critical government tasks, such as counting votes. Algebraic specification languages funded by DARPA via taxpayer money are being used to deal with the massive complexity of our nation's defense systems. If we really want democracy in this country, the same taxpayer-funded languages should be used as a foundation for designing our voting systems.

[Zhade]

17. Sorry if I seem dense (I'm not a programmer) --

Does o-o refer to an "object oriented" programming approach?

EDIT: Er, duh, I missed the sentence where you mentioned object-oriented. Heh, silly me. :)

[scottxyz]

14. At this point...

...as a programmer, I'm starting to think we should just give the voter a marble or a token and let them throw it into a slot marked Dem or Repub or Green, like at the post office, where each slot feeds into a different barrel.

Keep some observers around to make sure there's no hanky-panky.

At the end of the day, weight the different barrels and see who wins.

[Pobeka]

19. I had that thought too.

Need a means of dispensing the tokens so each voter only gets one per race.

[scottxyz]

6. Addendum (too late to go back and edit!)

Diebold's voting system, lacking referential integrity and unique indexes (hence lacking a database schema or specification) is a classic example of an implementation in search of a formal specification. Database systems developed without a schema have no "contract" between users and developers. In most cases, such projects simply fail.

INSERT THIS SENTENCE AT THE END OF THE ABOVE PARAGRAPH: In an implementation lacking a specification, this failure can of course simply go undetected.

[never cry wolf]

10. Thanks scottxyz

For a very non-techie you have explained things quite nicely. I don't understand everything but you put programming in terms i can understand as an architect. In my profession we also need to design to our users' needs and those need to be ferreted out and defined up front. Our term for this is our clients "program" which is analagous to your "specification." If this is not right, or at least close, the project will inevitably fail. Once a program is defined it can be tweaked but it is the guide that is necessary to start with and often is the basis of a contract.

Our schema may result in a physical layout as to size of floor plate, locations of the various elements of their operation, location of utilities and structure, relationships of these elements to each other and their interface with the exterior site constraints and codes, meanwhile our interfaces would be analagous to the interior decorating and exterior aesthetics within that defined space.

Well, I am certainly off topic here and really have nothing to add to the tech portion except that designers seem to have certain proceedures inherent in all fields of endeavor. I have also had enough math to follow your math analogy.

Mainly I wanted to thank you for making that last point clear to me. What you said in your original post is true to all designers.

"(Aside: Bad programmers talk a lot of gobbledygook but good programmers are surprisingly comprehensible. If you can't understand what a programmer is telling you, they're probably programming themselves into corner and/or trying to con you out of your money and/or your data.)

Thanks!!

on edit: rambling a bit, spellun, and want to add bad design is bad design, be it diebolt or skidmore.

[scottxyz]

13. I'm a non-architect

...but I loved Christopher Alexander's "A Pattern Language". (He seems to appeal to a lot of programmers.)

As you mention, the basic idea about specifications and implementations is not just applicable to the (young) science of computer programming.

In architecture as well as many other fields ranging from civil engineering to catering, both professionals and laypersons are accustomed to the separate notions of:

- "what" should be done; and

- "how" 'it' should be done.

There are many names for the "what" - in architecture, you say it is the "program", which serves as the basis of a contract and can then be tweaked. (I have worked on typing up detailed construction specs back when I used to work in a word-processing center, and it makes total sense to me that you can't put up a tall building without a formal spec written in the professional language of architecture - not just a vague proposal presented in English accompanied by lots of hand-waving).

I think it's important for us to drive this point home regarding professional specifications and implementations - in any field, be it architecture or computer programming.

Nobody makes big buildings without some kind of formal plan written in a highly specialized language. (The client might not be able to write this plan themselves - but you can be damn sure they read it and sign off on it.)

The same is true for programming: you can't write a database without writing a schema. Whenever I write a database, I sit down and write out a schema first, and there's always one or more people on the client side who are computer-literate enough to examine it, critique it, recommend changes, and finally sign off on it.

If builders were able to put up a building without submitting a blueprint for signoff, there might be a building standing there, but there would be no way to establish whether this was indeed the building the customer wanted.

If database developers were able to present a mish-mash of spaghetti code without submitting a schema for signoff, there might be a program running on the screen, but there would be no way to say whether it does what it's supposed to do.

Most software projects routinely go through a needs and requirements phase. And just like a vague, paragraph-based document in English isn't considered something a construction client can sign off on to authorize a building going up, in the same way a vague, paragraph-based document in English isn't something a software client can sign off on to authorize a program being written.

The database schema is the spec. Diebold - unlike nearly all other "professional" programming outfits - made no effort to provide this sort of formal spec to be signed off on. They couldn't have - because they didn't put referential integrity into their system - which is like designing a building without beams.

Here is a standard work (which non-programmers involved in needs & requirements or QA) refer to a lot for programming projects:

http://www.amazon.com/exec/obidos/tg/detail/-/0471052906/qid=1064445680/sr=1-1/ref=sr_1_1/104-9287504-8183146?v=glance&s=books

The Data Modeling Handbook : A Best-Practice Approach to Building Quality Data Models
by Michael C. Reingruber (Author), William W. Gregory (Author)

You can't design a big software system without someone on-board doing the stuff described in this book. This book is all about converting English text descriptions like "Every INVOICE belongs to a VENDOR" to diagrams of a little Invoice table hanging off a Vendor table, and passing this diagram around among the users to make sure everyone's happy with it.

There were no such diagrams in the Diebold software development process for these voting systems. The crucial element in the diagram - the line connecting the INVOICE table to the VENDOR table - was never drawn, so there was actually no diagram to hand around. That's like building a building without putting any beams in the corners. That's all I need to know to know these Diebold systems are garbage.

[lanlady]

15. in a nutshell, you're saying that--

--the Diebold software violates the basics of database design?

OK, let me play devil's advocate here. The voting software is designed for a simple purpose--to keep tallies of votes. Straightforward addition, really. For that you don't need RIs and parent/child relationships. You just need an adding machine and an audit log.

Why does the discussion need to veer into DB design issues? Presuming the voter's demographic data is not being tied to his/her vote. Or is the Diebold software trying to capture info about the VOTER, not just the vote?

[scottxyz]

18. Rebuttal to the "devil's advocate" argument

In a nutshell:
It's all about "built-in" versus "roll-your-own"

What's the best way to compute 13 times 48 in a computer program?
(a) Write 13*48
(b) Write 48+48+48+48+48+48+48+48+48+48+48+48+48


In-depth
Let's look at this "devil's advocate" argument. You point out that the software is simply supposed to "keep tallies of votes", or perform "straightforward addition". This is absolutely correct.

Many databases, such as the vendor-invoice database in the example in the original post, do just that - keep a tally of things such as invoices or amounts, and perform straightforward addition.

Expanded example: a simple vote-tallying system
For a voting-system application, it would be of course better to translate the vendor-invoice example to a candidate-ballot example.

A ballot can include many candidates, and a single candidate can be selected (voted for) on many ballots. This gives rise to a three-table schema:

CANDIDATE (parent)

BALLOT (parent)

CANDIDATE_SELECTED_ON_BALLOT (child to both CANDIDATE and BALLOT)

Slightly more complex than the vendor-invoice example in the original message, but all the same principles apply.

(You mention the possibility that the software might track the VOTER's info - but you're right in assuming that isn't tracked at all. In this simplified example, the parent tables would be CANDIDATE and BALLOT and the child table would be CANDIDATE_SELECTED_ON_BALLOT. No 'VOTER' table would be used.)

Many novice programmers, when confronted with such a simple task like tallying and subtotalling a bunch of records, do it the easy way you described, and leave out the referential integrity. Usually with more or less disastrous results.

Real-world experience shows that after many records have been added to a system with no referential integrity, you usually get the problems illustrated in the example in the original post. A significant percentage of the invoice records (=CANDIDATE_SELECTED_ON_BALLOT) end up having garbage vendor (=CANDIDATE) data, and they quietly drop out of all totalling calculations.

In the example, it's actually impossible to "keep a tally" of all the invoices (=CANDIDATE_SELECTED_ON_BALLOT) for a particular vendor (=CANDIDATE) or perform "straightforward addition". There's no requirement enforced on the invoice (=CANDIDATE_SELECTED_ON_BALLOT) table that only valid, non-blank vendor (=CANDIDATE) names can be used.

Two ways to prevent invoices (or ballots) from dropping out:
Declarative referential integrity - or "roll your own"
There are many ways to prevent this sort of error from happening in a database. In MySQL, for example, which lacks declarative referential integrity, the programmer can "roll their own" referential integrity - essentially by putting code on every single invoice (=CANDIDATE_SELECTED_ON_BALLOT) input screen that goes around and checks the vendor (=CANDIDATE) table to make sure that the vendor (=CANDIDATE) indeed exists. (For this reason, many programmers prefer to describe MySQL as a mere "file" system, not a database, despite its database-sounding name.)

All databases except MySQL offer a better way: declarative referential integrity. (In particular Microsoft Access offers this, via a simple checkbox - which Diebold failed to check.)

What's better about declarative referential integrity is three-fold:

(1) It's declarative. That means the programmer just has to check a box to get referential integrity and prevent "orphaned" invoice (=CANDIDATE_SELECTED_ON_BALLOT) records, rather than writing {procedural} code. Checking a box is a lot easier than writing your own code.

(2) It follows the design principle of "one fact in one place". There is only one thing you want to do here - guarantee that every invoice (=CANDIDATE_SELECTED_ON_BALLOT) has a valid vendor (=CANDIDATE) on it. It's easy to see that checking a single box to do this on the back-end (the single database schema) is less error-prone than writing code on every single data-entry screen on every single version of the front-end to provide this same integrity. Yes, theoretically, this integrity could be enforced via many lines of procedural code spread all around every single different version of the front-end. No programmer in their right mind would do it this way though, because there are other things to do in the software development process besides endlessly repeating the same code all over the program. If there's only one place to go to implement this functionality (and only one place to go to double-check that it indeed did get implemented) the software has a chance of being delivered on-time and without bugs.

If you turn the software development process into a game of Twister out of some desire to do things the hard way, either (a) on some screens the {procedural} referential integrity may be inadvertently omitted, (b) on some screens the {procedural} referential integrity may be omitted on purpose, or (c) the time the programmers and the certifiers waste tracking down the non-standard {procedural} referential integrity code on every screen on every version of the front-end will cut into other tasks, and, in the real world, this just means bugs.

A database, while it may have many front-ends (for users, for administrators), has only one back-end. Fortunately, referential integrity can be implemented with a single click in the back-end.

(3) It's built-in. The code which implements {declarative} referential integrity is part of the database management system (DMBS) itself. It's programmed by Microsoft (or whoever the DBMS vendor is). As such, although we know Microsoft isn't perfect, after 10 years of using Microsoft Access (or other vendors' DBMSs) we've reached an excellent consensus that this feature works. "Roll-your-own" integrity (inserting code on each screen in each version of the program, and checking all the records to make sure none are corrupt) would have to be written by the application developer (eg, Diebold). Programmers do not avoid using built-in functions in favor of rolling their own, for this obvious reason. Better to use the tried and true rather than rolling your own.

Another example of the advantages of "built-in" vs. "roll-your-own"
Implementing multiplication on your own (using addition)
By the same token, a "devil's advocate" could correctly point out that the built-in operator provided for performing some other basic operation (such as, say, multiplication) doesn't necessarily have to be used. Yes, you could "roll your own" multiplication operator - after all, this is a "straightforward" function, and a vendor such as Diebold could easily implement it by just replacing it with repeated calls to the addition operator. 5 times 7 COULD indeed be calculated by the programmer as 5+5+5+5+5+5+5 (or 7+7+7+7+7), instead of letting the language do it by writing 5*7. While certainly possible, this isn't a very appealing approach, for obvious reasons.

In a nutshell: Any person who knows arithmetic would be surprised (and suspicious, and possibly litigious) to find that a programmer had bypassed the built-in multiplication operator in favor of some "roll-your-own" approach involving multiple, potentially confusing and error-prone calls to the addition operator. Likewise any person who knows about tables, columns and relationships would be surprised (and suspicious, and possibly litigious) to find that Diebold had bypassed the built-in referential integrity control in favor of some "roll-your-own" potentially confusing and error-prone approach involving multiple calls to God-knows-what procedures.

In the case of this hypothetical do-it-yourself multiplication operator, it actually wouldn't be that hard for a certifier or user to quickly see whether an error was made - because multiplication problems typically involve just two inputs and any child can verify the output on a cocktail napkin.

But in the present case of Diebold's very real do-it-yourself (or completely missing, from what I am told) referential integrity controls, it would be very hard for an administrator or certifier to quickly see whether an error was made - because totalling records typically involves aggregating thousands of records into a total, and it's very hard to make sure that a bunch of records didn't drop out because of faulty or missing referential integrity.

Another use of declarative referential integrity:
Preventing the deletion of ballots
There is a VERY important use of declarative referential integrity missing from the original post: There is an extra checkbox in MS-Access and most other database management systems under "Enforce Referential Integrity". This extra checkbox lets the programmer choose between "Cascade DELETE" or "Cascade RESTRICT". If "Cascade RESTRICT" is checked, you can't delete a vendor if there's any invoices under it. If "Cascade DELETE" is checked, deleting a vendor makes all that vendor's invoices automatically vanish as well.

This means that a correct specification for a voting system would check the "Cascade RESTRICT" referential integrity checkbox on the relationship between parent table BALLOT and child table CANDIDATE_SELECTED_ON_BALLOT. By doing this, it is easy to verify that it is impossible to delete filled-in ballots.

One final note: Database schema as "formal specification"
Look up formal methods of software specification on google and you will see that this is a very active field:

http://www.google.com/search?hl=en&lr=&ie=UTF-8&oe=UTF-8&q=formal+methods+software+specification

Just like buildings are constructed according to a plan, and cakes are usually baked according to a recipe, programs are now implemented according to a specification. (Computer programming is only about 40 years old - so much younger a science than construction or baking! - which is probably the main reason why there are still practitioners hanging on who are unaware of the central importance of specification. Programming consultants who are unaware of this don't often get a second project from a client - if indeed they manage to deliver the first project. In a few years, there won't be any programmers this ignorant left.)

A software specification can be informal (a user "needs and requirements" document, often written in plain English). In the case of databases, a convenient formal language exists for specifications, called the "entity relationship (E-R) model". A translation of this language, one step closer to the machine, is called "SQL" (structured query language), and specifications written in this language are actually executable.

The "entity relationship model" and its executable cousin "SQL" are wonderful things. They are so close to English that many non-programmers can read E-R diagrams, intelligently critique them, and often even edit them. E-R diagrams are simple: they just show tables, columns, and relationships between the tables. (Powerful and simple: think Goethe: "In der Beschränkung zeigt sich erst der Meister" - "It is in self-limitation that a master first shows himself."*) Each relationship in this diagram can also be double-clicked, to let the programmer check a box that says "Enforce Referential Integrity" and also possibly check "On Cascade RESTRICT". This declarative referential integrity also shows up in the E-R diagram - so certifiers have only one place to go to easily verify that it's impossible to delete a vendor who has invoices (or a ballot which has candidates selected on it).

On the other hand, much as it it would be tedious to the point of error-prone to verify that 48+48+48+48+48+48+48+48+48+48+48+48+48 is indeed an equivalent "roll-your-own" notation for the standard built-in notation "13*48", it is doubtful that an approach (such as Diebold's) which scattered the enforcement of referential integrity in hundreds of lines of code all over the system (rather than using the standard built-in approach of checking the "Enforce Referential Integrity" checkbox) would meet even a liberal interpretation of the notion of compliance with government regulations mandating certification.

The E-R diagram is readily available in Access - just go into Tools > Relationships. Another few clicks of the mouse and the E-R diagram turns into an SQL program, which is immediately executable on the computer.

Diebold's vote-tallying software didn't do it this way - they left out the declarative referential integrity. They left out the diagram - and hundreds of poor souls are reduced to poring over thousands of lines of source code trying to figure out what on earth it does. Diebold left out the specification of the system, and furnished just an implementation. By leaving out the schema, which is where the declarative referential integrity checkbox gets checked, Diebold left out the "WHAT" that this system is supposed to do - and only provided the certifiers with the "HOW" it does {whatever it does}.

Does the delivered system satisfy the specification? This is an empty question - because there is no formal specification here to satisfy!

This is like constructing a building without a blueprint - or calculating 5*7 by doing 5+5+5+5+5+5+5. Yes, at some level it is possible to do it this way, and in the end you may get a building or a total. However, it's just asking for errors (you might get a crooked shack, or the wrong answers 30 or 40 rather than 35, or a certain percentage of the records might fall out and you'll never notice). A knowledgeable software purchaser would either fire or sue a programmer who wrote a multi-table database to do tallying without (a) declaratively setting (via a checkbox) referential integrity and (b) providing the resulting entity-relationship diagram for user/certifier sign-off.

* http://home.t-online.de/home/humanist.aktion/zitate6.htm
http://www.brainyquote.com/quotes/quotes/j/johannwolf125413.html

[Pobeka]

21. If I was going to do this, this is how I'd do it:

I'd have a simple ascii file on the computer, one for each race.

Each record on the file would contain the name, or unique ID of the candidate voted for.

The software would present the voter with races, one by one, and simply append the voter's choice for each race to the file.

At the end of the day, sum up the total records which match each candidate in each race.

That's the easy part, probably can do the summaries in under 100 lines of code.

The user interface part, which presents the user with choices, is maybe another 500 lines of code at most?

And, if you'll let me use Perl instead of C, I could cut the lines of code in about half.

But let's assume I code this in C. I'll bet we could show the source code to gobs (aka "a lot") of non-programmers and they would easily understand what's going on. A whole boatload (aka "millions") of programmers would be able to peer review the code an in under an hour declare the code should work, given no compiler, linker, or OS run-time issues.

Like you said upstream of here, this is not a complicated programming task.

[Zhade]

16. EXCELLENT. Thanks for posting this - very useful and understandable.

The main point I come away with is that Diebold (and anyone who fails to perfect a schema as the first step) is basically building the house before making sure the foundation won't crack and crumble.

Good stuff. Thanks again!

[scottxyz]

20. Exactly right, Zhade

The schema is the foundation or blueprint of a database.

Certifiers - and perhaps more importantly users - who might not be able or willing to wade through thousands of lines of the source code (which just glues the screen, reports and menus together) can quite easily critique a schema.

The first step to getting the software programmed right is signing off on the schema. Diebold evidently failed to even make a schema (which is where they should have, but didn't, turn on the referential integrity) - let alone furnish a schema to the certifiers and users.

As we get deeper into the question of "source code" (which would be a good thing - currently the source code is "proprietary" - hence the term "black box" voting), it will become clearer that there are many different iterations or versions of the source code for a given programming task - where typically each successive version is "closer" to the (final, pretty much unreadable, "low-level") machine language.

The notion of a "specification" and an "implementation" should become more important - where a {"lower-level"} implementation is simply a translation of a {"higher-level"} specification, done in such a way that the implementation "satisfies" the specification.

The highest-level specification of a database system - and hence the easiest to read, edit and certify - is the database schema.

When we get to the point where we finally have affirmed our inalienable right to see the source code (like any other non-classified government information), the first source code to look at for a database is the schema.

As Peruvian congressman Dr. Edgar David Villanueva so eloquently put it, talking about "the republican principle of openness to the public..."

In conformance with this universally accepted principle, the citizen has the right to know all information held by the State and not covered by well-founded declarations of secrecy based on law. Now, software deals with information and is itself information. Information in a special form, capable of being interpreted by a machine in order to execute actions, but crucial information all the same because the citizen has a legitimate right to know, for example, how his vote is computed or his taxes calculated. And for that he must have free access to the source code and be able to prove to his satisfaction the programs used for electoral computations or calculation of his taxes.

http://www.theregister.co.uk/content/archive/25157.html

[4dog]

22. This is both beautiful and enlightening.

I haven't done any programming since semi-advanced BASIC 15 years ago because it all got too complicated for me. It is encouraging to know that this progress has been made and the Bill Gates model need not prevail.

However, I can't recall when beautiful or sensible or sound had much traction with politicians. Maybe things will work out in the long run (if there is one).

[BigLed]

23. Phew

This was heavy wading for this non-tech but you make it as understandable as I could hope for. For me the key question you asked is this, "(1) Referential integrity pays off big time, and takes less than a minute to implement. (So WHY doesn't Diebold use it?)"

Why, indeed. I can think of two answers. 1. Utter and incomprehensible incompetence. 2. Intent to defraud.

I keep a quote on my desk at work where I am a technical resource for the public on insurance related questions and hear many, many people toss the "fraud" word around willy nilly, mostly because of lack of knowledge or understanding. In this discussion, my understanding, or rather lack thereof, of the technical aspects certainly makes it possible that I am guilty of jumping to a wrong conclusion about motives here.

The quote is from Napolean. "Never attribute to evil that which can be explained by incompetence."

Practically speaking it makes no difference at this time which it is in this case of black box voting and I think Bev knows this when she fights the conspiracy theory characterizations foisted upon her. We need to stop implementaion of this voting method from proceeding any further and most people will believe the problem defined as an issue of incompetence much more readily than that it is evil or that fraud has already occurred.

Myself, I believe in Murphy's law that if it can go wrong it will and a corollary that if evil people are given the opportunity to do evil, they will. (The reaction of Diebold to raising the question of auditability reinforces my belief of the intent to defraud.)

Beyond the practical it of course does matter if there is an intent to defraud and it matters even more if fraud has occurred already. But we can only take that on after we stop this now.

Bigled.

[Eloriel]

24. Oh, I think the memos point pretty clearly to intent to

defraud.

Anyway, I'm reminded of a conversation I had once upon a time with a corporate lobbyist at the state level. We found ourselves at a legislative reception and were commiserating about the level of, um, "intelligence" among the legislators, in general.

He said something to me that I thought about for a very, very long time: "Remember, nobody does something stupid on purpose."

It was a valuable lesson. However, he only had it half right. No, people don't do stupid things on purpose. But they DO do mean, self-seving and greedy things on purpose.

Good work, Scotty. Are you up to writing up a bit of a proposal that can be floated to certain Congressmembers and others?

Eloriel

[scottxyz]

25. Also, remember Diebold makes lots of ATMs

When's the last time you found an ATM that made a mistake in your bank balance?

Diebold has plenty of experience doing the most demanding database work. They just didn't choose to apply this experience to their voting software.

That's how we know it's fraud, not incompetence on their part.

[BigLed]

26. Don't get me wrong

I think it's fraud as well. I just think to avoid being accused of being tinfoil hat conspiracy theorists it's better to focus on stopping the spread of a terribly flawed program...at this stage. I'm practical first. Stopping this is most important, then comes proving fraud, which is much harder to do.

[scottxyz]

27. Yeah, I personally feel it's fraud but I'd settle for proving incompetence

I agree that while it may be fraud, all we really have to prove is incompetence.

If a programmer wrote a job like this for a client, they wouldn't really be interested in why the programmer screwed up so bad. They'd just fire him.

[BigLed]

29. A much easier case to prove

since you don't have to prove intent, a state of mind.

The internal emails I have seen do go a long way toward proving that though.

And a swift kick. I have a much better grasp of the technical issues thanks to your incredible ability to explain this, hopefully others will too.

[dusty64]

28. Over my head technically, but

:kick: nonetheless.