Can a device prove the identity of its own code? Say you have a computing system that has some functionality that is not in itself cryptographically secure, but you want to make sure is executed as specified, and, e.g. an adversary hasn't re-flashed the software when you weren't looking. An example might be a voting machine for a non-crypto scheme, or verifying that a motherboard is running the factory's firmware. 

Is there any sort of data or verification protocol that can be used to prove which version of the software is being run, that doesn't require physically disassembling the hardware, and is resilient against even an attacker who knows about it and who specifically designs their variant software to try to spoof it?

If nothing about the hardware (and its capacity) is known ahead of time, then AFAIK this is impossible because the attacker can just virtualise the entire "correct" software and return whatever it produces. (Although please correct me if this isn't true) Since that's not a very interesting scenario, instead assume 


Both the verifier and the attacker have complete access to the "correct" software in machine code form. 
The machine's memory capacity is fixed and known ahead of time by both verifier and attacker. (Or more generally, the machine's hardware configuration is known, and the attacker has not modified it except via software reprogramming)
If a handshake is involved, the verifier can be a trusted computer of arbitary capacity, not necessarily a human. (And so any computations the verifier has to do can be complicated so long as they're efficient.) 
If the system's "correct" software has to be prepared in some unusual but efficiently doable way beforehand for the scheme to work, assume that has happened by the verification step. 
Solutions that can be implemented in pure software are prefered, but solutions involving "small" hardware changes would also be acceptable. (Assume that simply replacing the program memory with ROM wasn't an option for whatever reason) 


(As an example of what I'm looking for, one possible solution for this problem that occured to me was to construct the software image as normal, then pad it with random data up to the capacity of the machine's program memory. To verify, the verifier then provides the system a random number, the machine then computes the hash of that number prepended to the entire contents of its program memory (which it can't spoof because there's nowhere to store the "correct" copy to reproduce for this step) and gives that to the verifier. The verifier can then verify the hash the machine has given it against its own calculation. I haven't thought very hard about the implications of this scheme though, or how to attack it, so I think I'm missing some flaw in it. I'd also like to see if it's possible to achieve the same outcome without relying on there being a reasonably small capacity to fill.)
No, a device can't "prove the identity of its own code" assuming no hardware modification, if we want this secure and achieved automatically from arbitrary software image made available in machine form representing what's supposed to be the executable code, at least when said image is in part adversarially built (and arguably neither if it is built per common practice).

Whatever remotely gives demonstration of what code is running must be inherently trusted; it can not attest of its own integrity, as thought in the question.

The question's "As an example.." method has a weakness: some of the data hashed can be selectively rebuilt during the hash, rather than really present. The code for the modified hashing part would hash content of actual memory for the bulk of the software image, but synthesized data in the two zones (A) where itself is and (B) where some of the genuine hashing code was supposed to be (actually modified, e.g. by at least a JMP to modified hashing code in A). At runtime, A and B are never actually hashed/checked. A contains the modified hash code and data necessary to reconstruct what's synthesized when apparently hashing A or B; that data includes a copy of the original B, and a compressed form of what A contains in the arbitrary software image made available in machine form (it is impossible to automatically detect that it is not actually functional code/data).

The above argument assumes that the arbitrary software image made available in machine form was prepared specially to make the insertion of the modified hash code easy, using zone A of software that has no real functional value and instead is a placeholder for something adversarially prepared. However, the attack might often be possible assuming only that the software image contains a zone of sufficiently compressible data or code. I'm willing to accept that the attack could not be carried if the entire software image was initially crafted by a non-attacker taking care to code densely; but that goes against modern software construction practice.



The OP is explicitly targeting integrity of the software of voting machines. An example is this one, which (with different software) is still used in France in several cities (Le Havre, Brest..). The entire software is in a socketted EPROM. The integrity of the software is "demonstrated" by the software computing and displaying a CRC of itself on the display. That's of course a complete joke against an adversarial attack (and using a hash would not help much, for the code displaying the hash can be replaced by code displaying the appropriate constant).

The method proposed by the question (where the value displayed depends on a manual entry) would seem, on the face of it, to mitigate the attack where a modified software displays the hard-coded CRC or hash of the software it mimics. However, for the reasons I explain, that's not cryptographically strong against a skilled adversary. And worse, the challenges fed for remote attestation could be used as a side channel to control the rigging of the votes.



That interesting "yes" answer achieves its goal by adding a Trusted Platform Module (a secure CPU with a private key capable of signing, a certificate, and trusted code), and most importantly assuming integrity of trusted boot code of the main CPU, the CRTM. My reasoning above assumed non-integrity of all software, only integrity of hardware.

Integrity of trusted boot code makes a qualitative difference. That boot code can verify the integrity of the rest of the code by verifying a digital signature, with the public key (or the root of a chain of certificates) in the trusted boot code. That's in wide use (e.g. in Point of Sales terminals since the 1990s) and is a reasonably effective measure against unauthorized code modification. This alone is however not achieving what the question asks: that method can't remotely attest that any software is running; it only insures that  only authorized software could run. And it remains quite vulnerable to modification/tampering, by debug mechanism allowing code injection (JTAG port, extra memory dynamically brought into the addressable space by a paging mechanism), and exploitation of software vulnerability bringing hostile code e.g. by buffer overflow (mitigation to the later are possible with Harvard architecture separating code and data, security rings, virtual machines, code proofs..).

To add attestation, the standard and working method is adding a capability to sign with a private key. A simple conceptual model is that the trusted boot code includes a Virtual Machine (e.g. JavaCard), verifies (by checking code signature as above) what code can run in that VM, and remotely attests of what it launched there together with a challenge to prevent replay (preferably by cryptographically signing or MACing, which requires a secret somewhere); it may even dynamically peek at what's in the VM and attest about it. Interpretation in a VM is not essential; principles for hardware equivalents running at native speed  are known since 1960's mainframes. The TPM-locked PC can be viewed as a refinement of that, allowing remote attestation of what is running, under hypothesis reasonable on a consumer PC, including that some code responsible of the attestation is not altered.