投票系统的实用 XML 数据设计和操作
作者： | 加入时间：2004-8-29 | 出自：IBM | 察看： 54
[当前：1 | 共：1] 分页：上一页 | 下一页 [URL=http://www.theit.cn/html/type_36/info_1481_1.html]1[/URL]
本期文章中，David 讨论了他为 EVM2003 自由软件项目开发相关 XML 数据格式的实践经验，这个项目的目的是开发能够生成选民可验证的选票的投票机。文中介绍了构造格式子集的一些设计原则，此外，David 还考察了如何通过编程让特定的应用程序与 XML 文档等价，以及为什么只有标准是不够的。
过去的 11 个月中，我参与了一个称为 [B]Open Voting Consortium(OVC) 的组织和一个称为 [B]EVM2003 的与自由软件有关的项目。OVC 的目标是取代专有供应商的封闭源代码电子投票机，尤其是那些无法提供选民可验证选票的产品。OVA 组织最初将重点放在美国国内选举上，但它也希望将来能将 OVA 系统用于其他国家。developerWorks 的读者都很清楚，软件很容易出错和受到恶意的攻击。对于选票被直接错误地只记录到电子存储设备上这样的风险，“请相信我们”是一个难以令人满意的答案。
EVM2003 项目是一个世界性社区研究计划，宿主在 SourceForge 上，目标是创建一个符合 OVC 给出的一组规范的选举软件的参考实现，该组织希望其自身能够成为选举系统的某种标准体。EVM2003 是使用 Python（带有各种不同的支持库）编写的，并使用 XML 来满足几乎所有的数据存储/配置需求。
OVC 规范十分详细，其中一些细节仍然在演化中。像安全性分析和完全威胁模型之类的问题不在本文的讨论范围之内，这些问题由世界上一些计算机安全和选举技术的顶尖级专家去认真考虑（包括您在这些领域所做的贡献）。在深入探讨支持目标系统的 XML 格式和源代码之前，有必要简要地介绍一下想像中的系统。本期文章中的代码和格式仅是初步的尝试，虽然某些细节很可能会改变，但是我希望其中的多数设计能够保留在投票系统中，最终为美国或者其他国家的选民所使用。
目前 OVC 已经公开演示了其参考设计，而我们也正与一些基金代理组织进行合作，如国家科学基金（National Science Foundation）、州立大学、管理机关，以及州立法机关或者联邦立法机关。
与 OVC 兼容的投票点应该包含几种类型的计算机工作站。投票站同时还将提供 GUI/触摸屏界面，以及帮助不便阅读的选民（如盲人）通过耳机和按键进行投票的界面。在选民投票之后，无论哪种类型的工作站都应该打印出正式的选票。看得见字并且识字的选民可以阅读选票上的内容，确认是否记录了自己的选择；作为一种替代方法，阅读不便的选民可以将选票拿到单独的、不联网的选票阅读工作站，通过听筒阅读选票的内容。一经确认，选票就被锁到票箱之中。结束一天的投票工作时，选务工作者将核对正式的选票，并对 EVM 中的匿名电子记录进行处理 —— 统计废票、测试选票等，以便针对作弊提供额外的检查。在高层上，如国家或州，选区被集中到一起（按照选举的术语称为“拉选票（canvassing）”），并且将对选票进行其他各种完整性检查。
EVM2003 和 XML
下面介绍 EVM2003 系统的工作原理。EVM2003 使用或者生成三种密切相关的 XML 文件：
选票文件。
电子选票图像（EBI）文件。
重新构造的选票图像（REBI）文件。
在初始阶段，在给定的地点/选区和日期进行的选举（可能是为某个特定党派投票）是数据驱动的，通过[B]选票文件来实现。在生产阶段中，该文件应该使用惟一的名称，指出选举的地点、日期、党派（如果合适的话）和自然语言（在提供多语言选票的地方）。例如，生成式选票 XML 数据文件可以有一个类似 election-20041102-US-MA-Franklin-2390-Dem-EN.xml 或者 election-20041102-US-MA-Hampshire-3451-Rep-ES.xml 的名称。这种精确的命名约定只是我的设想，但是其中包含了我所需要的那些数据类型（所有的识别信息也都包含在这些数据文件中，因此 XML 可能保存在（比方说） RDBMS 中，而不是保存在文件系统中）。
在选民投票之后，会有一个[B]电子选票图像（EBI）被作为 XML 文件保存在投票工作站上；存储的所有 EBI 都被写入可移动介质中，如 CD-R，写入的顺序是随机的，以确保选民的匿名性。虽然选票可能包含各种不同的格式（如字体选择、对齐方式、标尺和包围框），以便在视觉上使选民的身份验证更容易，但包含在 EBI 中的信息应该与打印的正式选票中的信息完全匹配。
在核对的过程中，选务工作者扫描选票生成[B]重新构造的选票图像（REBI）。即便没有错误，这些 REBI 也不一定在每一个位上都和相应的 EBI 完全相同。比如，在演示系统（产品系统也可能如此）中，我们决定使用条形码来表现选举，以简化扫描工作；但是，我们的条形码只记录了补名选举这件事，而没有记录补上的名字。何时以及是否计算补选的名字的权限有很大不同，因此建立边界条件要求人工检查选票上补入的名字是一种很好的方式。
EBI 和 REBI 与选票文件之间有着特殊的、非常微妙的关系。EBI 或者 REBI 基本上是选票文件的一个真子集，也就是说，只需要从选票文件中去掉非选择性选项，将根元素从 <ballot> 重新命名为 <cast_ballot>，就可以创建一个 EBI。这种关系体现在称为 <cast_ballot> 的 XML 文件上，该文件是选票 XML 文件的简化版本。在 EVM2003 的当前 CVS 快照中，有几个地方违背了上述的子集关系，但只要稍加修改就可以确保这种关系的成立。比如，在 ballot-election.xml 中，<contest> 元素中有一个元素 allow_writein，对于 EBT 或者 REBI，这个元素是多余的，并且它们不包含该元素。相应地，根元素 <cast_ballot> 包含一个属性 source ，可以用它来区分 EBI 和 REBI（比如分别使用 voting_machine 和 ballot_scan)。
如果在产品系统中强制实施真子集关系，可以提供一个相当不错的特性：如果保证基本的一致性，选票文件和 EBI 将遵循同样的 DTD/模式。虽然我们认为精确的子集关系并非必需的，但 EBI 和选票 XML 文件的密切相似性会使开发人员的调试和开发变得更容易（对于我们脆弱的记忆力也是如此）。
XML 示例
通过一些具体的 XML 文件可以帮助您理解我所描述的格式。正式的 DTD 或者模式（最好在产品中使用 RELAX NG）仍然在不断改变，对此我不准备过多讨论。为了节省空间，我简化了对 OVC 所使用的选举的演示，但至少为每种类型保留一个例子。首先来看一下选票文件：
清单 1. ballot-election.xml
<ballot election_date="2008-11-04" country="US" state="CA"
county="Santa Clara County" precinct="2216">
<contest ordered="No" coupled="Yes"
allow_writein="Yes" name="Presidency">
<selection party="Reform"
name="President">Martin Luther King</selection>
<selection party="Reform"
name="Vice President">John Anderson</selection>
<selection party="Workers"
name="President">Helen Keller</selection>
<selection party="Workers"
name="Vice President">Amelia Earhart</selection>
<selection party="Socialist"
name="President">V. I. Lenin</selection>
<selection party="Socialist"
name="Vice President">Karl Marx</selection>
</contest>
<contest ordered="No" coupled="No"
allow_writein="Yes" name="Senator">
<selection party="Green">Frances E. Willard</selection>
<selection party="Libertarian">Lucy Stone</selection>
<selection party="Democrat">Karl Menninger</selection>
<selection party="Labor">William Lloyd Garrison</selection>
</contest>
<contest ordered="No" coupled="No" allow_writein="No"
name="Transportation Initiative">
<summary>
<scope>Constitutional Amendment Article X, Section 19</scope>
<type>initiative</type>
<title>California Transportation Initiative For Statewide Solar
Powered Magnetic Levitation System</title>
</summary>
<description>
To reduce traffic and increase travel alternatives, this amendment
provides for development of a high-speed solar powered magnetic
levitation system to run along Interstate 5. Construction to begin
November 1, 2004.
</description>
<selection>Yes</selection>
<selection>No</selection>
</contest>
<contest ordered="Yes" coupled="No" allow_writein="Yes"
name="County Commissioner">
<selection>William Hewlett</selection>
<selection>Steve Wozniak</selection>
<selection>William Shockely</selection>
<selection>Gordon Moore</selection>
<selection>Philip Kahn</selection>
</contest>
</ballot>
有必要对 <contest> 的一些属性进行进一步解释。竞选人可以是有序的，以允许进行分级优先投票。分级优先投票允许选民为候选人指定优先级（一级、二级、三级等）。有多种不同的方法用来划分等级（所有这些都不在本文的讨论范围之内），但 [B]Instant Runoff 可能是美国最常见的一种等级划分方法。无论如何，既然有一些权限使用分级优先投票，这种选票 XML 格式就需要适应这种情况。现有的选票 DTD 缺乏指出可分配的最大等级数的属性 —— 我将简要地说明如何添加该属性。
竞选人可以允许或禁止补名选票。在这个例子中，对于只能选择 Yes/No 的选票使用补名方式没有多大意义；其他类型的竞选人是否允许补名，要看选举规则而定。name 属性很简单 —— 它只用简单的几句话描述了竞选人。对于一些竞选人，可能还需要使用子元素向选民展示竞选人的细节信息（比如初步的描述）。同样，具体的内容与竞选规则有关。
coupled 属性似乎有点多余，但我们不清楚是否还有更好的办法。在美国总统大选中，我们使用了一个不太常见的系统，在该系统中，总统和副总统必须成对选择，尽管两个候选人的名字都出现在选票上，但不能照菜单 每次只选择一个。目前的设计把每个候选人列在一个 <selection> 元素中，但是，如果将 coupled 设置为 Yes，则候选人必须两个两个地出现，不能单独出现。
如前所述，投过的选票（EBI）基本上是原始选票的一个子集，但是也有少量的细节发生了变化。EBI 的命名不但包含选举的地点和日期，还包含一个不同的选票 ID number（在单个机器中不会重复使用）：
清单 2. v-20081104-US-CA-Santa_Clara_County-2216-1274.xml
<cast_ballot election_date="2008-11-04" country="US" state="CA"
county="Santa Clara County" precinct="2216"
number="1274" serial="213" source="voting_machine">
<contest ordered="No" coupled="Yes" name="Presidency">
<selection writein="No" name="President">V. I. Lenin</selection>
<selection writein="No" name="Vice President">Karl Marx</selection>
</contest>
<contest ordered="No" coupled="No" name="Senator">
<selection writein="No">William Lloyd Garrison</selection>
</contest>
<contest ordered="No" coupled="No" name="Transportation Initiative">
<selection writein="No">Yes</selection>
</contest>
<contest ordered="Yes" coupled="No" name="County Commissioner">
<selection writein="Yes">David Packard</selection>
<selection writein="No">Gordon Moore</selection>
<selection writein="No">William Hewlett</selection>
</contest>
</cast_ballot>
注意，属性 writein 目前出现在 <selection> 标签中。从某种意义上说，您可以观察相应的 ballot-election.xml 文件推断出是否是补名选举，该文件包含 <selection> PCDATA 内容，但它使用属性添加了一些有用的冗余。如果某个非补名候选人与原来的选票不匹配，这就是一个明确信号，指出您遇到了数据完整性问题。但是在一些选举规定中，如果满足特定的阈值（竞选人不相上下，全部都是补名选举候选人等），则只计算特定的补名选举候选人的名称；您可能不需要查看标记为 writein="Yes" 的选举内容。
比较 XML 选票
我曾经说过 EVM2003 是用 Python 编写的，此外，XML 访问是通过 Gnosis Utilities 库来完成的，具体说就是 gnosis.xml.objectify。通过这个库，对选票或者 EBI 文件的操作都变得非常简单。比如，可以使用下面代码将竞选人和候选人的信息加载到一些 Python 数据结构中：
清单 3. ballot-election.xml 到 Python 的转换
from gnosis.xml.objectify import make_instance
ballot = make_instance(xml_data)
contnames, cont = [], {}
for contest in ballot.contest:
name = contest.name
contnames.append(name)
if contest.coupled=="No":
cont[name] = [select.PCDATA for select in contest.selection]
if contest.allow_writein=="Yes":
cont[name].append("")
else:
cont[name] = []
for n in range(0, len(contest.selection), 2):
cont[name].append([s.PCDATA for s in contest.selection[n:n+2]])
if contest.allow_writein=="Yes":
cont[name].append(["",""])
通常，函数 make_instance() 会将 XML 化的数据格式压缩成一个行，该行之后的代码都是 Python 代码。
在将 EBI 互相比较或者将 EBI 与 REBI 进行比较时，出现一个特殊的问题（更准确地说，是几个相关问题）。如前所述，REBI 并不是在每一位上都与相应的 EBI 都相同，因为不能完全在条形码中记录补录的名字。不过更一般地说来，OVC 的目的是建立数据格式标准，而不只是用特定的代码生成数据。第三方代码也应该能够生成和处理 EBI，比如确定已经正确完成了制表。
文档等同问题出现在很多种 XML 文档中：根据应用程序的要求，何时两个文档相等？符合相同的 DTD 或者模式是最小的必要条件，同时，将 XML 规范化可以去除很多琐细的语法变化。但是作为一条准则，意义上的等价不能只凭借模式表达出来。比如，确定子元素的顺序什么时候有意义，什么时候是偶然的，这些就与具体的应用级别密切相关。
Gnosis Utilities 库提供了一个相当不错的（照我看来）自定义相等含义的方法。您可以定义一个带有相等和不等测试的自定义类，来包含带有根元素 <cast_ballot> 的所有 XML 文档。模块 evm2003.utils.equiv 将一个特定应用程序的相等测试添加到 EBI Python 对象中，同时，您还可以将该模块用作命令行工具来比较 EBI/REBI。下面列出了这个模块，其中包含一些详尽的注释：
清单 4. evm2003.utils.equiv.py 模块
"""Compare ballot XML files for equivalence
.
This file may be imported as a module or used as a command-line ballot
comparison tool. If imported, e.g.:
.
>>> import evm2003.utils.equiv
>>> from gnosis.xml.objectify import make_instance
>>> a = make_instance(scanned.xml)
>>> b = make_instance(stored.xml)
>>> a == b
1
.
At the command-line:
.
% python equiv.py scanned.xml stored.xml
.
(lack of any output means success, in that ultra-terse UNIX-philosophy
way).
.
We implement custom .__eq__() and .__ne__() methods specific to cast
ballots. Injecting such methods is the recommended technique for enhancing
gnosis.xml.objectify objects.
.
The files scanned.xml and stored.xml documents were used to test this.
They differ in several non-significant respects:
(1) the top-level attributes occur in a different order;
(2) non-ordered multi-select contests have selections in a different
order;
(3) Write-in votes have different PCDATA content (for example, nothing for
scanned.xml).
"""
import gnosis.xml.objectify
import sys
class cast_ballot(gnosis.xml.objectify._XO_):
def __eq__(self, other):
metadata = election_date country state county
number precinct serial.split()
for attr in metadata:
if getattr(self, attr) != getattr(other, attr):
return 0
by_name = lambda a, b: cmp(a.name, b.name)
self.contest.sort(by_name)
other.contest.sort(by_name)
for my, your in zip(self.contest, other.contest):
if my.name != your.name or \
my.ordered != your.ordered or \
my.coupled != your.coupled:
return 0
if my.ordered == "No":
# Compare non-writeins (but dont know if same num writeins)
my_select = dict([(x.PCDATA,None) for x in my.selection
if x.writein=="No"])
your_select = dict([(x.PCDATA,None) for x in your.selection
if x.writein=="No"])
if my_select != your_select:
return 0
continue
for my_select, your_select in zip(my.selection, your.selection):
if (my_select.writein, your_select.writein) == ("Yes","Yes"):
pass
elif my_select.PCDATA != your_select.PCDATA:
return 0
return 1
def __ne__(self, other):
return not self == other
#-- Namespace injection
gnosis.xml.objectify._XO_cast_ballot = cast_ballot
#-- Command-line operation
if __name__==__main__:
a, b = map(gnosis.xml.objectify.make_instance, sys.argv[1:3])
if a != b:
print sys.argv[1], "and", sys.argv[2], "are NOT equivalent ballots!"
我认为有了上面的那些说明，就不需要再详细地解释 EBI 等价的基本原理。示例代码足以说明许多 XML 处理应用程序中遇到的类似问题。
结束语
完全抛开 EVM2003 的政治含义，我对参与自由软件项目感到非常满意，在该项目中，XML 显然就是 适合 使用的数据存储格式。在很多情况下，强迫您使用 XML 似乎也是因为这个原因 —— 但只有很少的情况 XML 是绝对合适的。在与标准出现交叉的项目中，我认为 XML 的作用特别强大，因为有那么多可互操作的解析程序和绑定库可以使用（很多已经在本专栏中讨论过）。而在像 EVM2003 这样必须有自己的数据格式（而且数据量适中）的项目中，XML 再合适不过了。
参考资料
在 SourceForge 网站上阅读有关 EVM2003 项目 的文章，它希望为选举开发一个自由软件基础设施。
通过网站进一步了解开放投票联盟（Open Voting Consortium）。
下载 Gnosis Utilities 作为归档文件，或者浏览 程序包，包括其文档。
通过developerWorks 专栏以前各期文章进一步了解 David 的 Gnosis Utilities。“将 XML 文档作为对象的“Python 化”处理 (II)”中介绍了模块 gnosis.xml.objectify （2000 年 8 月）。可以在“重温 xml_pickle 和 xml_objectify”中找到最新的讨论（2001 年 6 月）。最近，“使用 ElementTree，以 Python 语言处理 XML”中讨论了gnosis.xml.objectify 的性能和更新（2003 年 6 月）。
David 曾经与别人合写过两篇关于投票系统底层的安全和私密问题的学术论文，Open Voting Consortium 参考了这两篇论文：
“Privacy Issues in an Electronic Voting Machine”，与 Arthur M. Keller、Joseph Lorenzo Hall 及 Arnold Urkin 合写。
“A PC-Based Open-Source Voting Machine with an Accessible Voter-Verifiable Paper Ballot”，与 Arthur M. Keller、Alan Dechert 及 Karl Auerbach 合写。
在 developerWorks XML 专区可以找到数百篇 XML 文章。
在 developerWorks Developer Bookstore 可以找到各种有关 XML 的书籍，其中包括 David Mertz 所著的 Text Processing in Python。
了解如何才能成为一名 IBM 认证的 XML 及相关技术的开发人员。
[/B][/B][/B][/B][/B][/B]
[返回] 计算机科学论坛 →
XML.ORG.CN讨论区 - XML技术 → 『 XML源码及示例(仅原创和转载) 』 → 投票系统的实用 XML 数据设计和操作[转帖]
(订阅本版)
2005/5/23 21:27:00
新浪微博
投票系统的实用 XML 数据设计和操作[转帖]
