Search Results: "beh"

10 December 2013

Kees Cook: live patching the kernel

A nice set of recent posts have done a great job detailing the remaining ways that a root user can get at kernel memory. Part of this is driven by the ideas behind UEFI Secure Boot, but they come from the same goal: making sure that the root user cannot directly subvert the running kernel. My perspective on this is toward making sure that an attacker who has gained access and then gained root privileges can t continue to elevate their access and install invisible kernel rootkits. An outline for possible attack vectors is spelled out by Matthew Gerrett s continuing useful kernel lockdown patch series. The set of attacks was examined by Tyler Borland in Bypassing modules_disabled security . His post describes each vector in detail, and he ultimately chooses MSR writing as the way to write kernel memory (and shows an example of how to re-enable module loading). One thing not mentioned is that many distros have MSR access as a module, and it s rarely loaded. If modules_disabled is already set, an attacker won t be able to load the MSR module to begin with. However, the other general-purpose vector, kexec, is still available. To prove out this method, Matthew wrote a proof-of-concept for changing kernel memory via kexec. Chrome OS is several steps ahead here, since it has hibernation disabled, MSR writing disabled, kexec disabled, modules verified, root filesystem read-only and verified, kernel verified, and firmware verified. But since not all my machines are Chrome OS, I wanted to look at some additional protections against kexec on general-purpose distro kernels that have CONFIG_KEXEC enabled, especially those without UEFI Secure Boot and Matthew s lockdown patch series. My goal was to disable kexec without needing to rebuild my entire kernel. For future kernels, I have proposed adding /proc/sys/kernel/kexec_disabled, a partner to the existing modules_disabled, that will one-way toggle kexec off. For existing kernels, things got more ugly. What options do I have for patching a running kernel? First I looked back at what I d done in the past with fixing vulnerabilities with systemtap. This ends up being a rather heavy-duty way to go about things, since you need all the distro kernel debug symbols, etc. It does work, but has a significant problem: since it uses kprobes, a root user can just turn off the probes, reverting the changes. So that s not going to work. Next I looked at ksplice. The original upstream has gone away, but there is still some work being done by Jiri Slaby. However, even with his updates which fixed various build problems, there were still more, even when building a 3.2 kernel (Ubuntu 12.04 LTS). So that s out too, which is too bad, since ksplice does exactly what I want: modifies the running kernel s functions via a module. So, finally, I decided to just do it by hand, and wrote a friendly kernel rootkit. Instead of dealing with flipping page table permissions on the normally-unwritable kernel code memory, I borrowed from PaX s KERNEXEC feature, and just turn off write protect checking on the CPU briefly to make the changes. The return values for functions on x86_64 are stored in RAX, so I just need to stuff the kexec_load syscall with mov -1, %rax; ret (-1 is EPERM):

#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
#include <linux/init.h>
#include <linux/module.h>
#include <linux/slab.h>
static unsigned long long_target;
static char *target;
module_param_named(syscall, long_target, ulong, 0644);
MODULE_PARM_DESC(syscall, "Address of syscall");
/* mov $-1, %rax; ret */
unsigned const char bytes[] =   0x48, 0xc7, 0xc0, 0xff, 0xff, 0xff, 0xff,
                                0xc3  ;
unsigned char *orig;
/* Borrowed from PaX KERNEXEC */
static inline void disable_wp(void)
 
        unsigned long cr0;
        preempt_disable();
        barrier();
        cr0 = read_cr0();
        cr0 &= ~X86_CR0_WP;
        write_cr0(cr0);
 
static inline void enable_wp(void)
 
        unsigned long cr0;
        cr0 = read_cr0();
        cr0  = X86_CR0_WP;
        write_cr0(cr0);
        barrier();
        preempt_enable_no_resched();
 
static int __init syscall_eperm_init(void)
 
        int i;
        target = (char *)long_target;
        if (target == NULL)
                return -EINVAL;
        /* save original */
        orig = kmalloc(sizeof(bytes), GFP_KERNEL);
        if (!orig)
                return -ENOMEM;
        for (i = 0; i < sizeof(bytes); i++)  
                orig[i] = target[i];
         
        pr_info("writing %lu bytes at %p\n", sizeof(bytes), target);
        disable_wp();
        for (i = 0; i < sizeof(bytes); i++)  
                target[i] = bytes[i];
         
        enable_wp();
        return 0;
 
module_init(syscall_eperm_init);
static void __exit syscall_eperm_exit(void)
 
        int i;
        pr_info("restoring %lu bytes at %p\n", sizeof(bytes), target);
        disable_wp();
        for (i = 0; i < sizeof(bytes); i++)  
                target[i] = orig[i];
         
        enable_wp();
        kfree(orig);
 
module_exit(syscall_eperm_exit);
MODULE_LICENSE("GPL");
MODULE_AUTHOR("Kees Cook <kees@outflux.net>");
MODULE_DESCRIPTION("makes target syscall always return EPERM");

If I didn t want to leave an obvious indication that the kernel had been manipulated, the module could be changed to:

not announce what it s doing
remove the exit route to not restore the changes on module unload
error out at the end of the init function instead of staying resident

And with this in place, it s just a matter of loading it with the address of sys_kexec_load (found via /proc/kallsyms) before I disable module loading via modprobe. Here s my upstart script:

# modules-disable - disable modules after rc scripts are done
#
description "disable loading modules"
start on stopped module-init-tools and stopped rc
task
script
        cd /root/modules/syscall_eperm
        make clean
        make
        insmod ./syscall_eperm.ko \
                syscall=0x$(egrep ' T sys_kexec_load$' /proc/kallsyms   cut -d" " -f1)
        modprobe disable
end script

And now I m safe from kexec before I have a kernel that contains /proc/sys/kernel/kexec_disabled.

2013, Kees Cook. This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 License.

Russ Allbery: krb5-sync 3.0

krb5-sync is the software we run at Stanford to synchronize principal information from a central Heimdal realm to Active Directory, allowing users to use either a Linux-based Kerberos environment or Active Directory with the same account and password. The original intent of this release was to add a new feature to allow a subsidiary instance of an account in the MIT or Heimdal realm to be synchronized with the instance-less account in Active Directory. This allows, for example, an rra/windows instance to be used to set and maintain the password for an rra principal in Active Directory. In the process of implementing that, though, I ended up doing a significant overall of the code, since the plugin architecture was quite awkward and dated. The code now uses the MIT Kerberos data structures in a more natural and native way, since MIT Kerberos has now added direct support for plugins of this sort. Kerberos contexts and Kerberos error codes are used uniformly throughout the plugin, which provides consistent and more robust error handling and reporting. I also significantly enhanced the test suite, although it still needs more work to test the core functionality that has complex external dependencies. This release also drops support for all versions of MIT Kerberos prior to 1.9, which required an external patch; to run krb5-sync 3.0, you should upgrade to a recent version of MIT Kerberos. This allowed me to drop support for the legacy API. There are a couple of major backward-incompatible changes in this release (and both unfortunately are not handled automatically by the Debian package upgrade, since it's hard to find and safely modify KDC configuration). First, the ad_ldap_base configuration option is now mandatory when synchronizing account status and its meaning has changed. Previously, dc elements for the realm were appended to a provided partial base. Now, the complete DN of the root of the Active Directory tree should be provided. This is more flexible and more useful with a wider variety of Active Directory setups. Second, I took advantage of the backward-incompatibilities to change the module name to sync.so from krb5_sync.so, since the latter sounded weirdly redundant and verbose when installed in the Kerberos plugin directory. This will require a configuration change to the plugin configuration for the KDC or kadmin server. Also in this release are a couple of new options: ad_queue_only, which forces all changes to be queued for later processing instead of processed in real time, and syslog, which can be used to turn off the internal syslog logging of non-errors from the module. (This is mostly useful for test suites.) Now, password changes are queued on any Active Directory failure, not just a few oddly-distinguished ones. The previous behavior was rather specific to Stanford's needs, and queuing all password changes shouldn't pose any problems. Finally, the krb5-sync-backend utility program for manipulating the queued changes has been completely rewritten and is much cleaner. It now uses the Net::Remctl::Backend Perl module for command and option handling, so that module (provided with remctl 3.4 or later) must be installed. It also requires IPC::Run, which is available from CPAN. It uniformly supports a -d option to specify the queue location, and skips event files during processing that no longer exist. You can get the latest release from krb5-sync distribution page.

8 December 2013

John Goerzen: Results with btrfs and zfs

The recent news that openSUSE considers btrfs safe for users prompted me to consider using it. And indeed I did. I was already familiar with zfs, so considered this a good opportunity to experiment with btrfs. btrfs makes an intriguing filesystem for all sorts of workloads. The benefits of btrfs and zfs are well-documented elsewhere. There are a number of features btrfs has that zfs lacks. For instance:

The ability to shrink a device that s a member of a filesystem/pool
The ability to remove a device from a filesystem/pool entirely, assuming enough free space exists elsewhere for its data to be moved over.
Asynchronous deduplication that imposes neither a synchronous performance hit nor a heavy RAM burden
Copy-on-write copies down to the individual file level with cp --reflink
Live conversion of data between different profiles (single, dup, RAID0, RAID1, etc)
Live conversion between on-the-fly compression methods, including none at all
Numerous SSD optimizations, including alignment and both synchronous and asynchronous TRIM options
Proper integration with the VM subsystem
Proper support across the many Linux architectures, including 32-bit ones (zfs is currently only flagged stable on amd64)
Does not require excessive amounts of RAM

The feature set of ZFS that btrfs lacks is well-documented elsewhere, but there are a few odd btrfs missteps:

There is no way to see how much space subvolume/filesystem is using without turning on quotas. Even then, it is cumbersome and not reported with df like it should be.
When a maxmium size for a subvolume is set via a quota, it is not reported via df; applications have no idea when they are about to hit the maximum size of a filesystem.

btrfs would be fine if it worked reliably. I should say at the outset that I have never lost any data due to it, but it has caused enough kernel panics that I ve lost count. I several times had a file that produced a panic when I tried to delete it, several times when it took more than 12 hours to unmount a btrfs filesystem, behaviors where hardlink-heavy workloads take days longer to complete than on zfs or ext4, and that s just the ones I wrote about. I tried to use btrfs balance to change the metadata allocation on the filesystem, and never did get it to complete; it seemed to go into an endless I/O pattern after the first 1GB of metadata and never got past that. I didn t bother trying the live migration of data from one disk to another on this filesystem. I wanted btrfs to work. I really, really did. But I just can t see it working. I tried it on my laptop, but had to turn of CoW on my virtual machine s disk because of the rm bug. I tried it on my backup devices, but it was unusable there due to being so slow. (Also, the hardlink behavior is broken by default and requires btrfstune -r. Yipe.) At this point, I don t think it is really all that worth bothering with. I think the SuSE decision is misguided and ill-informed. btrfs will be an awesome filesystem. I am quite sure it will, and will in time probably displace zfs as the most advanced filesystem out there. But that time is not yet here. In the meantime, I m going to build a Debian Live Rescue CD with zfsonlinux on it. Because I don t ever set up a system I can t repair.

5 December 2013

Daniel Kahn Gillmor: The legal utility of deniability in secure chat

This Monday, I attended a workshop on Multi-party Off the Record Messaging and Deniability hosted by the Calyx Institute. The discussion was a combination of legal and technical people, looking at how the characteristics of this particular technology affect (or do not affect) the law. This is a report-back, since I know other people wanted to attend. I'm not a lawyer, but I develop software to improve communications security, I care about these questions, and I want other people to be aware of the discussion. I hope I did not misrepresent anything below. I'd be happy if anyone wants to offer corrections. BackgroundOff the Record Messaging (OTR) is a way to secure instant messaging (e.g. jabber/XMPP, gChat, AIM). The two most common characteristics people want from a secure instant messaging program are:

Authentication: Each participant should be able to know specifically who the other parties are on the chat.
Confidentiality: The content of the messages should only be intelligible to the parties involved with the chat; it should appear opaque or encrypted to anyone else listening in. Note that confidentiality effectively depends on authentication -- if you don't know who you're talking to, you can't make sensible assertions about confidentiality.

As with many other modern networked encryption schemes, OTR relies on each user maintaining a long-lived "secret key", and publishing a corresponding "public key" for their peers to examine. These keys are critical for providing authentication (and by extension, for confidentiality). But OTR offers several interesting characteristics beyond the common two. Its most commonly cited characteristics are "forward secrecy" and "deniability".

Forward secrecy: Assuming the parties communicating are operating in good faith, forward secrecy offers protection against a special kind of adversary: one who logs the encrypted chat, and subsequently steals either party's long-term secret key. Without forward secrecy, such an adversary would be able to discover the content of the messages, violating the confidentiality characteristic. With forward secrecy, this adversary is be stymied and the messages remain confidential.
Deniability: Deniability only comes into play when one of the parties is no longer operating in good faith (e.g. their computer is compromised, or they are collaborating with an adversary). In this context, if Alice is chatting with Bob, she does not want Bob to be able to cryptographically prove to anyone else that she made any of the specific statements in the conversation. This is the focus of Monday's discussion. To be clear, this kind of deniability means Alice can correctly say "you have no cryptographic proof I said X", but it does not let her assert "here is cryptographic proof that I did not say X" (I can't think of any protocol that offers the latter assertion). The opposite of deniability is a cryptographic proof of origin, which usually runs something like "only someone with access to Alice's secret key could have said X."

The traditional two-party OTR protocol has offered both forward secrecy and deniability for years. But deniability in particular is a challenging characteristic to provide for group chat which is the domain of Multi-Party OTR (mpOTR). You can read some past discussion about the challenges of deniability in mpOTR (and why it's harder when there are more than two people chatting) from the otr-users mailing list. If you're not doing anything wrong... The discussion was well-anchored by a comment from another participant who cheekily asked "If you're not doing anything wrong, why do you need to hide your chat at all, let alone be able to deny it?" The general sense of the room was that we'd all heard this question many times, from many people. There are lots of problems with the ideas behind the question from many perspectives. But just from a legal perspective, there are at least two problems with the way this question is posed:

laws themselves are not always just (e.g. consider chat communications between an interracial couple in the USA before 1967, if instant messaging had existed at the time), and
law enforcement (or a legal adversary in civil litigation) may have a different understanding or interpretation of the law than you do (e.g. consider chat communications between a corporate or government whistleblower and a journalist).

In these situations, people confront real risk from the law. If we care about these people, we need to figure out if we can build systems to help them reduce that legal risk (of course we also need to fix broken laws, and the legal environment in general, but those approaches were out of scope for this discussion). The Legal Utility of Deniability Monday's meeting was called specifically because it wasn't clear how much real-world usefulness there is in the "deniability" characteristic, and whether this feature is worth the development effort and implementation tradeoffs required. In particular, the group was interested in deniability's utility in legal contexts; many (most?) people in the room were lawyers, and it's also not clear that deniability has much utility outside of a formal legal setting. If your adversary isn't constrained by some rule of law, they probably won't care at all whether there is a cryptographic proof or not that you wrote a particular message (In retrospect, one possible exception is exposure in the media, but we did not discuss that scenario). Places of possible usefulness So where might deniability come in handy during civil litigation or a criminal trial? Presumably the circumstance is that a piece of a chat log is offered as incriminating evidence, and the defendant is trying to deny something that they appear to have said in the log. This denial could take place in two rather different contexts: during rules over admissibility of evidence, or (once admitted) in front of a jury. In legal wrangling over admissibility, apparently a lot of horse-trading can go on -- each side concedes some things in exchange for the other side conceding other things. It appears that cryptographic proof of origin (that is, a lack of deniability) on the chat logs themselves might reduce the amount of leverage a defense lawyer can get from conceding or arguing strongly over that piece of evidence. For example, if the chain of custody of a chat transcript is fuzzy (i.e. the transcript could have been mishandled or modified somehow before reaching trial), then a cryptographic proof of origin would make it much harder for the defense to contest the chat transcript on the grounds of tampering. Deniability would give the defense more bargaining power. In arguing about already-admitted evidence before a jury, deniability in this sense seems like a job for expert witnesses, who would need to convince the jury of their interpretation of the data. There was a lot of skepticism in the room over this, both around the possibility of most jurors really understanding what OTR's claim of deniability actually means, and on jurors' ability to distinguish this argument from a bogus argument presented by an opposing expert witness who is willing to lie about the nature of the protocol (or who misunderstands it and passes on their misunderstanding to the jury). The complexity of the tech systems involved in a data-heavy prosecution or civil litigation are themselves opportunities for lawyers to argue (and experts to weigh in) on the general reliability of these systems. Sifting through the quantities of data available and ensuring that the appropriate evidence is actually findable, relevant, and suitably preserved for the jury's inspection is a hard and complicated job, with room for error. OTR's deniability might be one more element in a multi-pronged attack on these data systems. These are the most compelling arguments for the legal utility of deniability that I took away from the discussion. I confess that they don't seem particularly strong to me, though some level of "avoiding a weaker position when horse-trading" resonates with me. What about the arguments against its utility? Limitations The most basic argument against OTR's deniability is that courts don't care about cryptographic proof for digital evidence. People are convicted or lose civil cases based on unsigned electronic communications (e.g. normal e-mail, plain chat logs) all the time. OTR's deniability doesn't provide any legal cover stronger than trying to claim you didn't write a given e-mail that appears to have originated from your account. As someone who understands the forgeability of e-mail, i find this overall situation troubling, but it seems to be where we are. Worse, OTR's deniability doesn't cover whether you had a conversation, just what you said in that conversation. That is, Bob can still cryptographically prove to an adversary (or before a judge or jury) that he had a communication with someone controlling Alice's secret key (which is probably Alice); he just can't prove that Alice herself said any particular part of the conversation he produces. Additionally, there are runtime tradeoffs depending on how the protocol manages to achieve these features. For example, forward secrecy itself requires an additional round trip or two when compared to authenticated, encrypted communications without forward secrecy (a "round trip" is a message from Alice to Bob followed by a message back from Bob to Alice). Getting proper deniability into the mpOTR spec might incur extra latency (imagine having to wait 60 seconds after everyone joins before starting a group chat, or a pause in the chat of 15 seconds when a new member joins) or extra computational power (meaning that they might not work well on slower/older devices) or an order of magnitude more bandwidth (meaning that chat might not work at all on a weak connection). There could also simply be complexity that makes it harder to correctly implement a protocol with deniability than an alternate protocol without deniability. Incorrectly-implemented software can put its users at risk. I don't know enough about the current state of mpOTR to know what the specific tradeoffs are for the deniability feature, but it's clear there will be some. Who decides whether the tradeoffs are worth the feature? Other kinds of deniability Further weakening the case for the legal utility of OTR's deniability, there seem to be other ways to get deniability in a legal context over a chat transcript. There are deniability arguments that can be made from outside the protocol. For example, you can always claim someone else took control of your computer while you were asleep or using the bathroom or eating dinner, or you can claim that your computer had a virus that exported your secret key and it must have been used by someone else. If you're desperate enough to sacrifice your digital identity, you could arrange to have your secret key published, at which point anyone can make signed statements with it. Having forward secrecy makes it possible to expose your secret key without exposing the content of your past communications to any listener who happened to log them. Conclusion My takeaway from the discussion is that the legal utility of OTR's deniability is non-zero, but quite low; and that development energy focused on deniability is probably only justified if there are very few costs associated with it. Several folks pointed out that most communications-security tools are too complicated or inconvenient to use for normal people. If we have limited development energy to spend on securing instant messaging, usability and ubiquity would be a better focus than this form of deniability. Secure chat systems that take too long to make, that are too complex, or that are too cumbersome are not going to be adopted. But this doesn't mean people won't chat at all -- they'll just use cleartext chat, or maybe they'll use supposedly "secure" protocols with even worse properties: for example, without proper end-to-end authentication (permitting spoofing or impersonation by the server operator or potentially by anyone else); with encryption that is reversible by the chatroom operator or flawed enough to be reversed by any listener with a powerful computer; without forward secrecy; or so on. As a demonstration of this, we heard some lawyers in the room admit to using Skype to talk with their clients even though they know it's not a safe communications channel because their clients' adversaries might have access to the skype messaging system itself. My conclusion from the meeting is that there are a few particular situations where deniability could be useful legally, but that overall, it is not where we as a community should be spending our development energy. Perhaps in some future world where all communications are already authenticated, encrypted, and forward-secret by default, we can look into improving our protocols to provide this characteristic, but for now, we really need to work on usability, popularization, and wide deployment. Thanks Many thanks to Nick Merrill for organizing the discussion, to Shayana Kadidal and Stanley Cohen for providing a wealth of legal insight and legal experience, to Tom Ritter for an excellent presentation of the technical details, and to everyone in the group who participated in the interesting and lively discussion. Tags: chat, deniability, otr, security

28 November 2013

Debian Med: Bits from Debian Med team (by Andreas Tille)

Some of these bits are a bit outdated but there is no point in hiding this information just because it is old. FOSDEM talkAndreas Tille had a talk at FOSDEM which is also Video recorded. A quite similar but updated talk was held at DebConf 13 (see below). Jabber interview by reporter from IndiaThere was an interesting interview between Rajeev Nair and Andreas Tille at So, 17.02.2013 Rajeev Nair is Business head of an health care journal in India held via jabber. Since this might serve as some nice FAQ about Debian Med here is a complete log of this interview (permission to publish it was granted). Article about Debian MedAs a consequence of the interview above the Debian Med team has assembled an article which was originally intended to be published in the Health Cafe journal but somehow this never happened. So we ended up with a nice article targeting at interested readers about Free Software in medicine with not necessarily informatics background. Since the article is considered to be of good quality and has consumed some time of several team members we are seeking for ideas for relevant places where to publish it. It is available as PDFas well as in SVN. Yearly sprint of Debian Med teamThis year we had our third sprint of the Debian Med team and all participants consider it a great success again. The sprint was in end of February and the individual reports are linked from the according wiki page. Since Andreas Tille was able to prove the nice effect of having face to face meetings in Debian teams in the team metrics graphs presented in his talks at DebConf (see below) we will keep on with this good tradition. The next sprint is scheduled for Friday 31st January until Sunday 2nd February in Stonehaven near Aberdeen. If you are interested to meet the people behind Debian Med and want to join us in developing packages which are helpful in health care and bioinformatics you are invited to join us. DebConf 13 in VaumarcusAndreas Tille had two talks with specific influence to Debian Med development(Debian Med as a success story for other Blends, How to attract new developers for your team (MoM, SoB). For those who want to read a full (and lengthy) report about DebConf 13 by Andreas Tille this is online in this blog article. Codefest of the Open Bioinformatics FoundationIvo Maintz and Steffen M ller organised the Codefest of the Open Bioinformatics Foundation in Berlin. About 40 contributors from all over the world attended, connecting the Debian community strongly with upstream. The event triggered a joint paper of participants to Sprints, Codefests and Hackathons alike, presented at the Nettab conference on Semantic, Social, and Mobile Applications for Bioinformatics and Biomedical Laboratories in Venice. Reupload unattended packagesAndreas Tille has mentored the GSoC student Emmanouil Kiagias and as a byproduct some Blends metadata were now kept in UDD. This has inspired some new tools and one of this was an UDD query to return all packages in the interest of the Blend ordered by date when they were uploaded. It has shown that there were packages hanging around in the package pool since five years. So some effort was done to check those packages which were not necessarily "buggy" according to BTS entries and so we were able to fix the following issues in about 20-30 packages:

Remove DM-Upload-Allowed fields
hardening
canonical Vcs fields
checking homepages / watch files
checking policy 3.9.4 (cme fix dpkg-control)
profit from xz compression in binary packages which makes perfectly sense in some of our packages
DEP5
DEP3
use dh consequently to simplify things for team members / NMUers
finally upload several changes in VCS but remained UNRELEASED
found several other hidden issues like

Since it was impressive how many things that deserve fixing are hidden in such long unattended packages it is recommended also to other teams to spend some time into these. The UDD query can be easily tweaked for a team maintainer address. Debian Med Bug Squashing Advent Calendar 2013The Debian Med team will again do the Bug Squashing Advent Calendar. Feel free to join us in our bug squashing effort where we close bugs while other people are opening doors. :-) Kind regards and see you at Debian Med sprint
Andreas.

27 November 2013

Steinar H. Gunderson: Stockfish

The open-source chess program Stockfish recently climbed to the top of the TCEC rating lists. Even though it does not seem likely to win the actual TCEC tournament (it is 15.5 11.5 down in the 48-game superfinal against Komodo, a closed-source commercial program, after winning 4, losing 8 and drawing 15), this is a tremendeous achievement. This is not only because it is highly unusual that the strongest chess program is open-source (it's naturally hard to keep a competitive edge when everybody can see your secrets!), but also because it is a mere 9000 lines of C++ code. (This is without a GUI; it interfaces through a standardized protocol known as UCI.) In comparison, Crafty, a far weaker open-source program, is about four times that, GNU Chess is above 40000, and I seem to recall that the Deep Blue program was something like 65000 lines (in addition to, of course, all the code for the ASIC chess chips it contained, and stood for the majority of its chess strength!). So, the development team is really to be commended. It should also be said that TCEC is testing the latest beta versions of most of these engines and while Stockfish is developed in the open, on GitHub, the latest versions of e.g. Komodo and Houdini are private. (This is probably one of the reasons why Stockfish is slightly lower on e.g. the CCRL list, which also computes chess program rating lists by playing games between them.) Now, why does anyone care? Only a very small handful of players would be able to score even a draw against any of these programs in a 10-game match, so does it really matter which one we choose? Or is this some obscure pissing contest? The answer, of course, is that these engines are not primarily useful for competitive play; they are useful for analysis. Almost any player, right down from beginners to the very top players, can benefit from having someone stronger than them look at their games (or others' games!) and say where things went wrong. (Somehow analyzing losses always seem more instructive than analyzing wins. Nobody ever got better by winning, as the saying goes.) And the better a program is at playing chess, the more likely is its analysis to be correct. Of course, for the weaker players, a chess coach is likely to produce much more understandable guidance ( this creates a weak square on c7 is much more palatable than after these 18 moves here, white is 0.48 pawns stronger than you, so this was a bad move , and engines produce the latter sort of output), but they are always available, incredibly strong, and cost much less than a coach. :-) They also add a lot to the otherwise quite hard-to-comprehend activity of watching high-level human players; while the computers do not understand every kind of position equally well, they at least provide some sort of objective verdict on which player has the upper hand, something which can be really hard to discern unless you have very strong players around for commentary. So, in trying to improve my skills a bit, I've been analyzing my games with engines for a while, and recently I've switched from Rybka to Stockfish. (Rybka, a closed-source program, used to be the clear leader of the pack, but after a huge amount of drama involving accusations of who has copied code from who, it seems no longer to be actively developed, and Stockfish is now somewhat stronger.) This, unfortunately, brings me to the things I don't like too much about Stockfish; it seems to behave more erratically than Rybka did in interactive analysis mode. Its score jumps a lot more around when I move something (worse at remember the analysis from the previous position?), and sometimes, it changes its mind a lot when I move back and forth between moves maybe the huge selectivity that makes chess engines so strong these days also make them behave less usefully when only looking at a move for a few seconds. So, even though Stockfish is a fantastic chess engine, and will only get better in the future, maybe I'll go back to Rybka at some point. But then again, maybe I should then check out Komodo or any of the other engines out there or maybe talk to someone who actually knows chess, that would help a lot, too =)

Timo Jyrinki: Workaround for setting Full RGB when Intel driver's Automatic setting does not work

Background I upgraded from Linux 3.8 to 3.11 among with newer Mesa, X.Org and Intel driver recently and I found a small workaround was needed because of upstream changes.

The upstream change was the Add "Automatic" mode for "Broadcast RGB" property, and defaulting to the Automatic. This is a sensible default, since many (most?) TVs default to the more limited 16-235, and continuing to default to Full from the driver side would mean wrong colors on the TV. I've set my screen to support the full 0-255 range available to not cut the amount of available shades of colors down.

Unfortunately it seems the Automatic setting does not work for my HDMI input, ie blacks become grey since the driver still outputs the more limited range. Maybe there could be something to improve on the driver side, but I'd guess it's more about my 2008 Sony TV actually having a mode that the standard suggests limited range for. I remember the TV did default to limited range, so maybe the EDID data from TV does not change when setting the RGB range to Full.

I hope the Automatic setting works to offer full range on newer screens and the modes they have, but that's probably up to the manufacturers and standards.

Below is an illustration of the correct setting on my Haswell CPU. When the Broadcast RGB is left to its default Automatic setting, the above image is displayed. When set to Full, the image below with deeper blacks is seen instead. I used manual settings on my camera so it's the same exposure.

Workaround For me the workaround has evolved to the following so far. Create a /etc/X11/Xsession.d/95fullrgb file:

if [ "$(/usr/bin/xrandr -q --prop   grep 'Broadcast RGB: Full'   wc -l)" = "0" ] ; then
/usr/bin/xrandr --output HDMI3 --set "Broadcast RGB" "Full"
fi

And since I'm using lightdm, adding the following to /etc/lightdm/lightdm.conf means the flicker only happens once during bootup:

display-setup-script=/etc/X11/Xsession.d/95fullrgb

Important: when using the LightDM setting, enable executable bits (chmod +x) to /etc/X11/Xsession.d/95fullrgb for it to work. Obviously also check your output, for me it was HDMI3.

If there is no situation where it'd set back to "Limited 16:235" setting on its own, the display manager script should be enough and having it in /etc/X11/Xsession.d is redundant and slows login time down. I think for me it maybe went from 2 seconds to 3 seconds since executing xrandr query is not cheap.
Misc Note that unrelated to Full range usage, the Limited range at the moment behaves incorrectly on Haswell until the patch in bug #71769 is accepted. That means, the blacks are grey in Limited mode even if the screen is also set to Limited.

I'd prefer there would be a kernel parameter for the Broadcast RGB setting, although my Haswell machine does boot so fast I don't get to see too many seconds of wrong colors...

23 November 2013

Mike Hommey: Don t trust python s os.execv

Python is nice and all, but its low-level functions have real disruptive discrepancies between platforms. Case at point:

import os
os.execvp("sh", ["sh", "-c", "exit 1"])

As a UNIXy person, I d expect running the above script to return an error code of 1. And I would be perfectly right on UNIX systems. On Windows, it returns 0. You d think such a difference in behavior would be documented? It s not. Thank you python.

22 November 2013

Vincent Sanders: Error analysis is the sweet spot for improvement

Although Don Norman was discussing designers attitude to user errors I assert the same is true for programmers when we use static program analysis tools.

The errors, or rather defects in the jargon, that a static analysis tools produce can be considered low cost well formed bug reports available very early in the development process.

When I say low cost it is because they can be found by a machine without a user or fellow developer wasting their time finding them. Well formed comes because the machine can describe exactly how it came to the logical deduction leading to the defect.
IntroductionStatic analysis is in general terms using the computer to examine a program for logic errors beyond those of pure syntax before it is executed. Examining a running program for defects is known as dynamic program analysis and while a powerful tool in its own right is not the topic of discussion.

This analysis has historically been confined to compiled languages as their compilers already had the Abstract Syntax Tree (AST) of the code available for analysis. As an example the C language (released in 1972) had the lint tool (released in 1979) based on the PCC compiler.

Practical early compilers (I am generalising here as the 19070s were a time of white hot innovation in computing and examples of just about any innovation in the field could probably be found) were pretty primitive and produced executables which were less good than hand written assembler output. Due to practical constraints the progress of optimising compilers was not as rapid as might be desired so static analysis was largely used as an external process.

Before progressing I ought to explain why I just mixed the concept of an optimising compiler and static analysis. The act of optimisation within those compilers requires program analysis, from which they can generate defect reports which we all know and love as compiler warnings, also explaining why many warnings only appear at higher optimisation levels where deeper analysis is required.

The attentive reader may now enquire as to why we would need external analysis tools when our compilers already perform the task. The answer stems from the issue that a compiler is trying to reconcile many desirable traits including:

Produce correct (expected) output from the source code for the target processor
Produce output which will execute using the smallest amount of resources possible (not just CPU time but memory access and cache usage)
Generate output in a reasonable amount of time.
Have a reasonable cost (both developer time and research into new methods) to implement the compiler itself.
Produce useful diagnostics

The slow progress in creating optimising compilers initially centred around the problem of getting the compiled output in a reasonable time to allow for a practical edit-compile-run-debug cycle although the issues more recently have moved more towards the compiler implementation costs.

Because the output generation time is still a significant factor compilers limit the level of static analysis performed to that strictly required to produce good output. In standard operation optimising compilers do not do the extended analysis necessary to find all the defects that might be detectable.

An example: compiling one 200,000 line C program with the clang (v3.3) compiler producing x86 instruction binaries at optimisation level 2 takes 70 seconds but using the clang based scan-build static analysis tool took 517 seconds or more than seven times as long.

Using static analysis

As already described warnings are a by-product of an optimising compilers analysis and most good programmers will endeavour to remove all warnings from a project. Thus almost all programmers are already using static analysis to some degree.

The external analysis tools available can produce many more defect reports than the compiler alone as long as the developer is prepared to wait for the output. Because of this delay static analysis is often done outside the usual developers cycle and often integrated into a projects Continuous Integration (CI) system.

The resulting defects are usually presented as annotated source code with a numbered list of logical steps which shows how the defect can present. For example the steps might highlight where a line of code allocates memory from the heap and then an exit path where no reference to the allocated memory is kept resulting in a resource leak.

Once the analysis has been performed and a list of defects generated the main problem with this technology rears its ugly head, that of so called "false positives". The analysis is fundamentally an undecidable problem (it is a variation of the halting problem) and relies on algorithms to generate approximate solutions. Because of this some of the identified defects are erroneous.

The level of erroneous defect reports varies depending on the codebase being analysed and how good the analysis tool being used is. It is not uncommon to see false positive rates, even with the best tools, in excess of 10%

Good tools allow for this and provide ways to supply additional context through model files or hints in the source code to suppress the incorrect defect reports. This is analogous to using asserts to explicitly constrain variable values or a type cast to suppress a type warning.

Even once the false positives have been dealt with there comes the problem of defects which while they may be theoretically possible take so many steps to achieve that their probability is remote at best. These defects are often better categorized as a missing constraint and the better analysis tools generate fewer than the more naive implementations.

An issue with some defect reports is that often defects will appear in a small number of modules within programs, generally where the developers already know the code is of poor quality, thus not adding useful knowledge about a project.

As with all code quality tools static analysis can be helpful but is not a panacea code may be completely defect free but still fail to function correctly.
Defect DensityA term that is often used as a metric for code quality is the defect density. This is nothing more than the ratio of defect to thousands of lines of code e.g. a defect density of 0.9 means that there is approximately one defect found in every 1100 lines of code.

The often quoted industry average defect density value is 1, as with all software metrics this can be a useful indicator but should not be used without understanding.

The value will be affected by improvements in the tool as well as how lines of code are counted so is exceptionally susceptible to gaming and long term trends must be treated with scepticism.
Practical examplesI have integrated two distinct static analysis tools into the development workflow for the NetSurf project which I shall present as case studies. These examples show a good open source solution and a commercial offering highlighting the issues with each.

Several other solutions, both open source and commercial, exist many of which have been examined and discarded as either impractical or proving less useful than those selected. However the investigation was not comprehensive and only considered what was practical for the project at the time.
clangThe clang project is a frontend to the LLVM project providing an optimising compiler for the C, C++ and objective C languages. As part of this project the compiler has been enhanced to run a collection of "checkers" which implement various methods of analysis on the code being compiled.

The "scan-build" tool is provided to make the using these features straightforward. This tool generates defect reports as a series of html files which show the analysis results.

Because the scan-build takes in excess of eight minutes on powerful hardware the NetSurf developers are not going to run this tool themselves as a matter of course. To get the useful output without the downsides it was decided to integrate the scan into the CI system code quality checks.

NetSurf CI system scan-build result list

Whenever a git commit happens to the mainline branch and the standard check build completes successfully on all target architectures the scan is performed and the results are published as a list of defects.

The list is accessible directly through the CI interface and also incorporates a trend graph showing how many defects were detected in each build.

A scan-build report showing an extremely unlikely path to a defect

Each defect listed has a detail link which reveals the full analysis and logic necessary to cause the defect to occur.

Unfortunately even NetSurf which is a relatively small piece of software (around 200,000 lines of code at time of writing) causes 107 defects to be emitted by scan-build.

All but 25 of the defects are however "Dead Store" where the code has a value assigned but is never checked. These errors are simply not interesting to the developers and are occurring in code generated by a tool.

Of the remaining defects identified the majority are false positives and several (like the example in the image above) are simply improbable requiring a large number of steps to reach.

This shows up the main problem with the scan-build tool in that there is no way to suppress certain checks, mark defects as erroneous or avoid false positives using a model file. This reduces the usefulness of these builds because the developers all need to remember that this list of defects is not relevant.

Most of the NetSurf developers know that the project currently has 107 outstanding issues and if a code change or tool improvement were to change that value we have to manually work through the defect list one by one to check what had changed.
CoverityThe coverity SAVE tool is a commercial offering from a company founded in the Computer Systems Laboratory at Stanford University in Palo Alto, California. The results of the original novel research has produced a good solution which improved on analysis tools previously available.

Coverity Interface showing summary of NetSurf analysis. Layout issues are a NetSurf bug

The company hosts a gratis service for open source projects, they even provide scans for the Linux kernel so project size does not appear to be an issue.

The challenges faced integrating the coverity tool into the build process differed from clang however the issue of execution time remained and the CI service was used.

The coverity scanning tool is a binary executable which collects data on the build which is then submitted to the coverity service to be analysed. This tool obviously relies upon the developer running the executable to trust coverity to some degree.

A basic examination of the binary was performed and determined the executable was not establishing network connections or performing and observably undesirable behaviour. From this investigation the decision was made that running the tool inside a sandbox environment on a CI build slave was safe. The CI system also submits the collected results in a compressed form directly to the coverity scan service.

Care must be taken to only submit builds according to the services Acceptable Use Policy which limits the submission frequency of NetSurf scans to every other day. To ensure the project stays within the rules the build performed by the CI system is manually controlled and confined to a subset of NetSurf developers.

Coverity connect defect management console for NetSurf

The results are presented using the coverity connect web technology based defect management tool. Access to the coverity connect interface is controlled by a user management system which precludes publicly publishing the results within the CI system.

Unfortunately NetSurf itself does not currently have good enough JavaScript DOM bindings to support this interface so another browser must be used to view it.

Despite the drawbacks the quality of the analysis results is greatly superior to the clang solution. The false positive rate is very low while finding many real issues which had not been previously detected.

The analysis can be enhanced by use of collection configuration and modelling files which remove intended constructions from consideration reducing the false positive rate to very low levels. The ability to easily and persistently suppress false positives through the web interface is also available.

The false positive management capabilities coupled with a user interface that makes understanding the defect path simple make this solution very practical and indeed the NetSurf developers have removed over 50 actual issues within a relatively short period since the introduction of the tool.

Not all of those defects could be considered serious but they had the effect of encouraging deeper inspection of some very dubious smelling source.
ConclusionsThe principle conclusions of implementing and using static analysis have been:

It is a powerful tool which aids programmers in improving their software.
It is not a panacea and bad code can have no defects.
It can suggest possible defects early in the development cycle.
It can highlight possibly problematic areas well before they affect a programs users.
The tool and the infrastructure around it have a large impact on the usefulness of the results.
The way results are presented has disproportionately significant impact on the usability of the defect reports.
The open source tools are good, and improving, but coverity currently provides a superior experience.
Integration into a projects CI system is beneficial.

When I started looking at this technology I was somewhat dubious about its usefulness but I have definitely changed my mind. It is a useful addition to any non-trivial project and the return on time and effort should be repaid handsomely in all but already perfect code (if you believe you have such code I have a bridge to sell you).

20 November 2013

Matt Zimmerman: Scaling Human Systems: Management

This is part 6 in a series on organizational design and growth.

The change from a business that the owner-entrepreneur can run with helpers to a business that requires management is a sweeping change. [...] One can compare the two kinds of business to two different kinds of organism: the insect, which is held together by a tough, hard skin, and the vertebrate animal, which has a skeleton. Land animals that are supported by a hard skin cannot grow beyond a few inches in size. To be larger, animals must have a skeleton. Yet the skeleton has not evolved out of the hard skin of the insect; for it is a different organ with different antecedents. Similarly, management becomes necessary when an organization reaches a certain size and complexity. But management, while it replaces the hard-skin structure of the owner-entrepreneur, is not its successor. It is, rather, its replacement. Peter Drucker

What it means Management is the art of enabling people to cooperate in achieving shared goals. I ve written elsewhere about what management is not. Management is a multifaceted discipline which is centered on people and the environment in which they work. Why it s important In very small organizations, management can be comparatively easy, and happen somewhat automatically, especially between people who have worked together before. But as organizations grow, management becomes a first-class concern, requiring dedicated practice and a higher degree of skill. Without due attention to management, coordination becomes excessively difficult, working systems are outgrown and become strained, and much of the important work described in this series just won t happen. Management is part of the infrastructure of the organization, and specifically the part which enables it to adapt and change as it grows. Old Status Quo People generally just do stuff , meaning there is little conscious understanding of the system in which people are working. If explicit managers exist, their jobs are poorly understood. Managers themselves may be confused or uncertain about what their purpose is, particularly if they are in such a role for the first time. The organization itself has probably developed more through accretion than deliberate design. New Status Quo People work within systems which help coordinate their work. These systems are consciously designed, explicitly communicated, and changed as often as necessary. Managers guide and coordinate the development and continuous improvement of these systems. The role of managers in the organization is broadly understood, and managers receive the training, support and coaching they need to be successful. Behaviors that help

It can be helpful to bring more experienced managers into the organization at this stage, especially if there isn t much management experience in house.
Show everyone in the organization (including managers themselves) what managers do and why it matters.
Consider very carefully whether someone should become a manager.
If someone does take on a management role, treat this as a completely new job, which requires handing off their existing responsibilities and learning a new discipline. Don t treat it as just an extension of their work. Write a new job description and discuss it up front.

Obstacles that stand in our way

Management misbeliefs
Granting promotions to management roles as rewards for performance
Many people, when they experience what management work is like, don t enjoy it and aren t motivated by it. It can be hard to predict when this will be the case, and people can feel trapped in a management role that they don t want. Make sure there are mechanisms to gracefully transition out of roles that don t fit for the people holding them.

19 November 2013

Carl Chenet: Yarn: a scenario testing tool

Follow me also on Twitter

Those who follow me on Twitter may have read my recent tweet about Yarn, a really nice software by Lars Wirzenius I discovered the last week-end while attending the Mini-Debconf UK in Cambridge. To make a long story short, Yarn allows the user to write scenarios of the executions of softwares. This scenario will be automatically played by Yarn which also returns the overview of the execution, with the goal to test the behaviour of these softwares. 1. Small example of how to use Yarn Let s have a look of how to use Yarn with a real example. The scenario will test if the software Brebis, a fully automatized backup checker, executes in an expected way. We can proceed as follow :

set up the test environment
launch a command with the software under test in the test environment
verify the execution of the test

This is an example of a Yarn scenario file, the file is formatted using the Markdown syntax:

    SCENARIO basic brebis execution
    GIVEN setting up brebis
    AND generating backup configuration with brebis
    WHEN brebis verifies a backup
    THEN verify brebis output
    IMPLEMENTS GIVEN setting up brebis
    hg clone http://hg.brebisproject.org $DATADIR/brebis
    mkdir -p $DATADIR/brebis/yarn-test
    cp $DATADIR/brebis/functional-tests/expected-generated-list-for-tar-archive/expected-generated-list-for-tar-archive.tar.gz $DATADIR/brebis/yarn-test
    IMPLEMENTS GIVEN generating backup configuration with brebis
    $DATADIR/brebis/brebis.py -G $DATADIR/brebis/yarn-test/expected-generated-list-for-tar-archive.tar.gz
    IMPLEMENTS WHEN brebis verifies a backup
    $DATADIR/brebis/brebis.py -c $DATADIR/brebis/yarn-test -l $DATADIR/brebis/yarn-test/brebis.log
    IMPLEMENTS THEN verify brebis output
    if [ -s $DATADIR/brebis/yarn-test/brebis.log ]; then return 1; else return 0; fi

2. Result of the execution of the Yarn scenario Yarn provides at the end of the scenario an overview of the execution, as show below: $ yarn brebis-scenario
Scenario test suite PASS, with 1 scenarios (4 total steps), in 16.4 seconds 3. Details of the Yarn scenarios The five first lines are basically your scenario. Each step takes a keyword and a sentence to identify a step. You define a name with the SCENARIO keyword. The next step, GIVEN, allows generally the setup of the test environment. It is possible of course to define different steps with the keywork AND. Once the environment setup has been completed, we launch the test with the keyword WHEN. At last we check the result of the execution with THEN. It is worth noting that if you need further steps after checking the result of the execution, you can use FINALLY. Very helpful while setting up the test environment is the variable $DATADIR, automatically initialized by Yarn. It provides the path to a temporary directory where you can store files during the execution of your scenario. This directory is by default removed at the end of the scenario. Now the real trick: at each step I described above is associated shell commands to execute thanks to the IMPLEMENTS keyword.It s in my opinion a great way to increase the understanding of what the scenario really does. In a short glance of the first lines, if the names of the steps are carefully chosen, you will understand what the scenario does without needing to read the actual shell code. Simple and efficient. 4. More about Yarn Yarn is written in Python and now available in Debian in the package cmdtest. The sources are available here. In my opinion, if you were looking for this kind of tool, Yarn is in a really good direction. This project is still young but the core features do the job and the upstream is eager to receive feedbacks (and patches) Some links:

The official webpage of cmdtest/Yarn

Source code of cmdtest/Yarn

Yarn README

Introduction to Yarn by his author Lars Wirzenius

Interested in Yarn? What do you think about it? Let us know in the comments of this post.

Francois Marier: Things that work well with Tor

Tor is a proxy server which allows its users to hide their IP address from the websites they connect to. In order to provide this level of anonymity however, it introduces latency into these connections, an unfortunate performance-privacy trade-off which means that few users choose to do all of their browsing through Tor. Here are a few things that I have found work quite well through Tor. If there are any other interesting use cases I've missed, please leave a comment!
Tor setup There are already great docs on how to install and configure the Tor server and the only thing I would add is that I've found that having a Polipo proxy around is quite useful for those applications that support HTTP proxies but not SOCKS proxies. On Debian, it's just a matter of installing the polipo package and then configuring it as it used to be recommended by the Tor project.
RSS feeds The whole idea behind RSS feeds is that articles are downloaded in batch ahead of time. In other words, latency doesn't matter. I use akregator to read blogs and the way to make it fetch articles over Tor is to change the KDE-wide proxy server using systemsettings and setting a manual proxy of localhost on port 8008 (i.e. the local instance of Polipo). Similarly, I use podget to automatically fetch podcasts through this cron job in /etc/cron.d/podget-francois:
0 12 * * 1-5 francois http_proxy=http://localhost:8008/ https_proxy=http://localhost:8008/ nocache nice ionice -n7 /usr/bin/podget -s
Prior to that, I was using hpodder and had the following in ~/.hpodder/curlrc:
proxy=socks4a://localhost:9050

GnuPG For those of us using the GNU Privacy Guard to exchange encrypted emails, keeping our public keyring up to date is important since it's the only way to ensure that revoked keys are taken into account. The script I use for this runs once a day and has the unfortunate side effect of revealing the contents of my address book to the keyserver I use. Therefore, I figured that I should at least hide my IP address by putting the following in ~/.gnupg/gpg.conf:
keyserver-options http-proxy=http://127.0.0.1:8008
However, that tends to makes key submission fail and so I created a key submission alias in my ~/.bashrc which avoids sending keys through Tor:
alias gpgsendkeys='gpg --send-keys --keyserver-options http-proxy=""'

Instant messaging Communication via XMPP is another use case that's not affected much by a bit of extra latency. To get Pidgin to talk to an XMPP server over Tor, simply open "Tools Preferences" and set a SOCKS5 (not Tor/Privacy) proxy of localhost on port 9050.
GMail Finally, I found that since I am running GMail in a separate browser profile, I can take advantage of GMail's excellent caching and preloading and run the whole thing over Tor by setting that entire browser profile to run its traffic through the Tor SOCKS proxy on port 9050.

16 November 2013

Lars Wirzenius: Debian: developing it wrong

This is an essay form of a talk I have given today at the Cambridge Mini-debconf. The talk was videoed, so will presumably show up in the Debconf video archive eventually. Abstract Debian has a long and illustrious history. However, some of the things we do perhaps no longer make as much sense as they used to do. It's a new millennium, and we might find better ways of doing things. Things that used to be difficult might now be easy, if we dare look at things from a fresh perspective. I have been doing that at work, for the Baserock project, and this talk is a compilation of observations based on what I've learnt, concentrating on things that affect the development workflow of package maintainers. Introduction and background I have been a Debian developer since August, 1996 (modulo a couple of retirements), and have used it a little bit longer. I have done a variety of things for Debian, from maintaining PGP 2 packages to writing piuparts to blathering excessively on the mailing lists. My day job is to develop the Baserock system at Codethink. Baserock is a set of tools and workflows for developing embedded and appliance Linux systems. If you squint, it looks a bit like a source-based Linux distribution. I have worked on Baserock since September, 2011. Some of Baserock's design has been influenced by my experience with Debian. With Baserock I have the chance to fix all the things that are wrong in Debian, and this talk is me giving back to Debian by pointing out some the things I feel should be fixed. I don't have solutions for these problems: this is a bug report, not a patch. It's also perhaps a bit of a rant. I am specifically concentrating here on technical and tooling issues that affect the development process of Debian. I excluding social issues. I am also not trying to get Debian to switch to Baserock. Baserock is targeting embedded and appliance systems, and makes simplifying assumptions based on those targets, which Debian does not get to do. I am pointing out problems, and I am outlining solutions as implemented in Baserock, when I think the concept carries over well to Debian. Build tools should be intelligent, packaging should be dumb In Debian, the fundamental tool for compiling the upstream code and assembling a binary package is dpkg-buildpackage. It uses debian/rules, which is a Makefile with targets with specific names and semantics. By executing the right targets in the right order, dpkg-buildpackage tells the source package to build the binary package. On the one hand, this is a nice design, because it abstracts away the large variety of upstream build systems into one API for dpkg-buildpackage to use. On the other hand, it puts all the intelligence for how packages are built into the packages. Making packaging intelligent, rather than the build tool, means packagers need to do more work, and there's more work to do when, say, the Debian policy changes, or when there are other changes that affect a large number of packages. If packaging is intelligent, then every package needs changes. If the build tool is intelligent, then you change the build tool and re-build everything. In Baserock we put as much intelligence as we can into the Morph tool, which drives the build process. It turns out that today, unlike in 1995, most upstream projects use one of a handful well-known build systems: autotools, cpan, cmake, Python distutils, etc. With just a little extra logic in Morph we avoid having any delta against upstream in Baserock. This doesn't work for quite all upstream projects, of course, but we've spent the 2% (two, not twenty) of effort that solves 80% of the problem. In recent years, the dh approach to packaging has made a lot of packages be able to have only a minimal, 3-line debian/rules file. This is excellent. Wouldn't it be nice if even that wasn't needed? It'd save thousands of files in source packages across the archive, at least. It would be easy to: if the file is missing, have dpkg-buildpackage assume the 3-line version by default. Getting rid of a single file is, of course, not a particularly big win. The big win is the change in mindset: rather than dealing with all new issues in development by adding yet more fields to debian/control and more optional, competing tooling outside the core toolset, if you improve the tools everyone uses, then everyone's packages gets better. The goal should, in my opinion, be that for the large number of packages where upstream uses a well-known, well-behaved build system, and uses it in a reasonably sensible way, the Debian source package should not require anything added to make the package build. There will still be a need to add some stuff, such as the debian/copyright file, to make a good Debian package, but just getting the package to build should require nothing extra. (Side note: wouldn't it be nice if there was a well-known, widely used way to mark up copyright information so that debian/copyright could be constructed and updated automatically?) Configuration file handling on upgrades: add ucf to dpkg already In the 1990s, dpkg had excellent handling of configuration files and merging local changes with changes from the new package version, but it was excellent only because it tried to do that at all, and mostly nothing else did. It hasn't changed much, since, and it's not excellent on any absolute scale. We have the ucf tool, which can do a better job, but requires to be added to each package wanting to use it. Why don't we make dpkg smarter, instead? If ucf is not not good enough to be merged wholesale into dpkg, let's write something better. Making every package maintainer use ucf manually is just wasteful. This is not the kind of thing that should be done for each package separately: the package manager should be smart so that packaging can be stupid. The goal should be that dpkg is smart enough in its configuration file handling that having the package do it is a very rare special case. Clean building shouldn't be hard The basic tool for building a package is dpkg-buildpackage. It is ever so slightly cumbersome to use, so there are some wrappers, most importantly debuild. However, if you're making a build intended to be uploaded to the Debian archive, you should be doing a clean build. This means having to learn, configure, and use yet more tools. A clean build is important: security updates, development, debugging, quality control, porting, and user support become more difficult if we don't know how a package was built, and can't reproduce the build. It gets harder to keep build dependencies correct, making it harder for everyone to build things. Luckily, Debian has solved the clean build problem. Unluckily, it has solved it multiple times, creating the problem of having to choose the clean building approach you want to use. The default way of building is not clean, so then you have to remember to use the non-standard way. You also get to spend time maintaining the clean build environments yourself, since that doesn't seem to be fully automated. None of this is hard, as such, but it's extra friction in the development workflow. The primary approaches for clean building in Debian seem to be pbuilder, cowbuilder, and sbuild. I happen to use pbuilder myself, because it's what's been around the longest, but I make no claim of having made an informed choice. That is part of the problem here: why should I have to spend the effort to become informed to make a choice well? Why is the default way of building not clean? Don't say performance: Morph sets up a clean staging area in seconds, and does not offer you a choice of not doing so. It's a chroot, with everything but the build tree hardlinked from cached, unpacked build dependencies, and protected using read-only bind mounts. What's more, this approach avoids having to maintain the pbuilder base tarballs or sbuild chroots manually. It's all automatic, and up to date, for every build. Furthermore, the staging area contains only the specified build dependencies, and not anything else, meaning a build fails if a build dependency is missing, rather than succeeding because it happens to be in the default set of packages the build tool installs. Mass building shouldn't be hard Suppose you want to try out a large-scale change in Debian. It might be trying out a new version of GCC, or using llvm's clang as the default C compiler, or updating glibc, or doing a large library transition such as a new version of GTK+, or trying a new dpkg version, or even something more exploratory such as changing the default optimisation flags for all packages to see what breaks. All of these will require you to at least rebuild all affected packages. Ideally you'd test the built packages as well, but let's concentrate on the building for now. Here's what you do. You make the changes you want to try out, and build those packages. You create a dedicated APT repository, and upload your packages there. You configure your build environment to favour that APT repository. You make a list of all reverse build dependencies of the packages you changed. You write a script to build all of those, preferably so that if you change A, and rebuild B, then you also rebuild C which build depends on B. Each rebuilt package you also upload to your APT repository. You keep track of the build log, and success or failure, of each build. The people in Debian who do this kind of stuff regularly presumably have tools for doing it. It shouldn't be a rare, special thing, though. If my package has reverse build dependencies, I should at least consider testing building when I'm making changes. Otherwise, it might take years until the reverse build dependencies are rebuilt, and the problem is only found then, making it harder to fix. To be fair, building a lot of packages takes a lot of resources. It's not feasible to rebuild everything in Debian every time there's any change to, say, eglibc. However, it's feasible to do it, for large subsets of the archive, without huge hardware investments. One VCS to rule them all In 1995 there was really only one relevant version control system: CVS. It was not a great tool. In 2000, another contender existed: Subversion. It fixed some problems in CVS, but still wasn't a great tool. In 2005, there was a great upheaval and distributed version control systems started to become mainstream. There were a large handful of them. In 2010, it was becoming pretty clear that git had won. It's ugly, but it's powerful. I'm not going to debate the relative merits of different version control systems. Until recently, I was a Bazaar boy, and all of my personal projects were kept in Bazaar. (I have recently switched everything to git.) There are, however, strong benefits from everyone using the same system. Developers don't need to learn a dozen version control systems. Tools that operate on many repositories are easier to write and maintain. Workflows become simpler if one system can be assumed. Debian has a strong historical tendency to choose every option. This is sometimes a good thing, and sometimes a bad thing. For keeping source packages in version control I believe it is to be a bad thing. The status quo is that a Debian source package may not be in version control at all, or it might be in any version control system. This is acceptable when everyone only ever needs to maintain their own packages. However, in a distribution the size of Debian, that is not the case. NMUs, security support, archive wide transitions, and other situations arise when I might need to change yours, or you might need to change mine. We try to work around this by having a complicated source package format, using quilt to maintain patches to upstream semi-manually in a debian/patches directory. This is an awkward workflow. It's a workflow that trips up those that are not used to it. (I know quilt is a patch management system, not a version control system. I think git does it much better anyway.) It would be oh so much easier if everyone kept their source packages in the same, real version control system. I don't even care what it is, as long as it is powerful enough to handle the use cases we have. Imagine a world where every Debian source package is kept, for argument's sake, git, and everyone also uses the same layout and roughly the same workflow to maintain it. What would this mean? It would mean that if you want to inspect the history of your package, you know how to do that. If you want to merge in some bugfix from upstream code, you know how to do that, without having to figure out which of the several source package formats are in use. It would make feasible the development of more powerful, more higher level tooling. For example, it would allow Debian to have what we call system branches in Baserock. In Debian we have stable, testing, unstable, and experimental. We may get something like Ubuntu's PPAs, or perhaps an improved version of those. These are very poor versions of system branches, just like quilt is a poor way to manage patches and deltas against upstream. For example, you can upload an experimental version of gccto experimental, but then nobody else can upload another experimental version. You can set up your own PPA for this, but you'll still be affected by all the uploads to unstable while you're working. A Baserock system branch is a branch of the entire system, or the entire distribution in the case of Debian. It is isolated from other system branches. In branch in an individual repository is a well-known concept. A system branch is conceptually like branching every repository in the distribution at once. The actual implementation is more efficient, of course. This would be possible to implement without standardising on one version control system, but it would be much harder to implement, and would have to live with the lowest common denominator for features. CVS and Subversion, for example, don't really to merges, where Bazaar, Mercurial, and git do. Possible does not mean feasible. Any work you do in a system branch is isolated. Your work doesn't affect others, and theirs doesn't affect yours, until a merge happens. This is a simple, but very powerful tool. Cheap system branches, and powerful merging, makes it possible to do experiments safely, with little fuss. Combine that with being able to build everything cleanly and quickly, and get into a situation where there's no need to have make technical decisions based on arguments on mailing lists, and instead they can be done by choosing by looking at working code. I don't know how this could be implemented in Debian, but think about it. If Debian could have this, it might many archive-scale changes easier. debian/rules clean: really? One of the silliest things we require of packages is that they have a debian/rules clean rule that cleans up after a build perfectly so that we can do repeated builds in the same source tree. Let's just use git clean -fdx instead. This is a problem that is superbly well suited for automation. There is no point whatsover making packagers do any manual work for this. Large scale semi-mechanical changes require too much effort About a decade ago, we decided to follow a new version of the Filesystem Hierarchy Standard and transition from /usr/doc to /usr/share/doc. This was an almost entirely mechanical change: in many cases, a mere rebuild would fix it, and in almost every other case it was just a minor tweak to the packaging. A one-line change. It took us seven years to do this. Seven years. Think about it. In a recent discussion about building R binary data files from source at package build time it was suggested that we take 2-3 release cycles to get this done. That's four to six years. Think about it. These are not isolated cases. Every time we need to make a change that affects more than a small handful of packages, it becomes a major undertaking. Most of the time all the people involved in this are agreeable to the change, and welcome it. The change takes long because it requires co-ordinating a large number of people. Sometimes people are just busy. Sometimes they've left the project, but haven't properly orphaned their packages. Waiting for a timeout for answers about packages drags the process longer. Mechanical changes, or semi-mechanical ones, which are very easy and very quick to do should not take years. They should take an evening, no more. There's no end of changes we might want to do like this. In 2005 and 2006 I filed a few hundred bugs from failed piuparts runs. They're still being fixed, even when the fix is simple, such as adding a postrm script to remove, when the package is purged, a configuration file created by postinst, or starting the service with invoke-rc.d rather than running an init.d script directly. Mostly one-line changes. There's more mechanical changes that might happen. For example, changing the value of the VCS-Browser field when the Debian version control server changes domain names. It's not just about simple, mechanical changes, either. Transitions of important library packages, for example, which require changes to reverse dependencies due to a changed API are another source of pain. What should be a few evenings of build fixes can drag out to months of co-ordination. This is caused partly by technical issues, and partly due to social issues. The main social issue is that we have quite a strong ownership of packages, and NMUs are to be done carefully, and only in some cases. This is both good and bad, and I won't discuss that aspect now. The technical issues are that our tools are primarily intended for maintaining individual packages, rather than all of them together, making it harder to make even simple changes in large number of packages. In addition to easy mass building and system branches, as outlined above, large-scale changes would require testing tools so that you don't build the new package versions, but also test things automatically. Essentially, CI at the distribution level. Conclusion I've listed above a small variety of problems I see in the Debian development processes and tools. They're not the important part of this talk. The important part is that it we, the Debian developers, should look at our tools, and workflows, critically, and improve them when we can. Even small improvements are very useful, when they affect each of our twenty thousand source packages. The important change I argue for here is one in mindset, rather than any specific problem in any tool. We need a mindset of constant, incremental improvement for our tools.

Russ Allbery: Review: Blue Remembered Earth

Review: Blue Remembered Earth, by Alastair Reynolds

Series: Poseidon's Children #1

Publisher: Ace

Copyright: January 2012

Printing: June 2012

ISBN: 0-441-02071-2

Format: Hardcover

Pages: 505
Geoffrey Akinya is one heir to the vast Akinya business empire, which straddles the solar system and has created vast riches from exploration and mining. He wants nothing to do with it. His passion is elephants: long and methodical study of wild herds in Africa, including a slow and careful investigation into their thought processes. His obnoxious and superior cousins have a passion for business and finance and can have the running of the company for all he cares. But Geoffrey's grandmother Eunice, the family matriarch and driving force behind much of their business expansion, has died. Her ashes are brought back to Africa from the Winter Palace in orbit around the Moon where she lived out her final days and scattered in a family ceremony. And, shortly thereafter, Geoffrey's cousins convince him to investigate a safe-deposit box left on the Moon by Eunice to ensure that it doesn't contain anything damaging to the family. What it contains is the first step in a puzzle. Despite himself, Geoffrey and his sister Sunday an artist and family black sheep who lives in a region of the Moon that is one of the sole holdouts against the ubiquitous monitoring common in the rest of the inhabited solar system are slowly pulled into unraveling that puzzle. This leads them into an uneasy alliance with one of the major political forces in the solar system and some startling revelations about their grandmother's actual plans. Blue Remembered Earth is another entry in the currently-popular sub-genre of solar system SF. Interstellar travel is still a dream, but a combination of improved technology, suspended animation, and heavy use of robots and robotic factories has let humans slowly expand into more of the solar system. On Earth, powers have risen and fallen, and the leap into the solar system coincided with a surging and powerful Africa. Extensive undersea colonization has established a new international consortium of sea-floor countries, and Earth politics have realigned into a diplomatic and business struggle between surface and oceanic nations. Unusually for this sort of fiction, most characters of significance in this story are African. The United States and Europe have quietly disappeared in the way that all non-US countries tend to in most other SF. Reynolds doesn't do very much with this setup (and the characters don't seem distinctly African to me). It's just there as the unremarked normal. I liked that. I kind of wish more of African culture had come through in the story, but there are enough SF novels with an assumed and unremarked white (and usually US) future that an assumed and unremarked black African culture is a nice change of pace. I picked up this book in part because it was described as a better 2312. That's a fairly accurate summary (although only helpful to those who have read Kim Stanley Robinson's novel). The scope and setting are similar, although Reynolds's future cuts back on the scope of off-world human colonization, relies more heavily on robotics, and keeps the power base on Earth. Both books are structured as a mystery, although in Blue Remembered Earth that mystery is deliberately planted for the characters. Reynolds is nowhere near as good at set pieces as Robinson, sadly. There's nothing here at the level of some of the scenes on Mercury in 2312. But he is much better at plotting and characterization, and Blue Remembered Earth tells a coherent story with increasing tension and a satisfying ending. Reynolds here uses an interesting strategy for spinning a mystery out of pieces of knowledge and discovery: set the discovery process prior to the novel, use protagonists who were unaware of it, and turn the details into a mystery that they have to investigate. This is an interesting way to address the problem that most discovery processes are slow and not particularly dramatic. It is artificial Eunice creates the plot for the novel but that worked for me. By the end of the book, I think I understand her reasons for doing so, and both Geoffrey and Sunday have good reasons to not be aware of any of the details before they start following the clues that Eunice leaves behind. The mystery of course sends Geoffrey and Sunday on a bit of a tour of the solar system as well as a tour of the past of their family business and the politics of the present. Here, Reynolds draws on an old SF idea: a conflict between groups that want to mechanize space exploration and groups that want to adapt humans for space. Long-time SF readers will be familiar with this approach, and I don't think Reynolds does anything startlingly new with it, but I thought it was a well-executed side plot. And, for once, an SF author realizes that Earth's oceans are as compelling of a place for that conflict to play out as outer space. There are, of course, significant mysteries to be uncovered, but it takes much of the book before those revelations start (even if one of them is almost spoiled in the dust jacket summary). The story up until that point is driven by character, particularly Geoffrey's stubborn annoyance at the rest of his family and his complete lack of interest in being the protagonist of a novel. I should probably warn here that many of the Amazon reviews disliked this book because of the characters, particularly Geoffrey. Apparently he comes across to some as whiny, resentful, and annoying. I, however, didn't have this reaction at all, possibly in part because I wholeheartedly share his opinion of both big business and his cousins. I thoroughly enjoyed reading an SF novel whose main characters are not driven either typical capitalist motives or a desire for personal exploration, but instead are pulled into the plot through a sense of loyalty and an inability to get out of the way of the problem. I also liked the way Reynolds manages to broaden and deepen the reader's appreciation for the characters as the story unfolds, and even salvages some characters I thought were unsalvageable. The last third of the book features some excellent plot twists and some very nicely-handled revelations. This is apparently the first book of a trilogy, and I had a suspicion at the end of the book that sequels were coming, but I think it stands on its own quite well. Most of the questions raised by the plot are resolved by the end of the book, and those that remain are of a size that other books have left unanswered intentionally. Despite not reaching the same moments of awe-inspiring beauty, and despite more workman-like descriptions, the stronger plot and more interesting characters do make Blue Remembered Earth a better 2312 for me. Given that 2312 won a Nebula, that's saying something (although I don't agree with that award). It's a bit deliberate in its pacing, and the plot built around a constructed puzzle can feel a bit artificial, but I think it's a solid and satisfying near-space SF novel. Followed by On the Steel Breeze. Rating: 7 out of 10

14 November 2013

Steve Kemp: Meanwhile, behind the facade of this innocent book store

In brief:

My partner and I had a hoot at the owl centre

I created a toy script which accepts HTTP POSTS to make a ring-buffer of JSON objects:

https://github.com/skx/4096.js

This will replace two similar but non-identical servers I run.

Tomorrow I have the day off work, as some visiting Finnish ladies are being tourists here in Edinburgh.

I will take the opportunity to photograph Edinburgh pubs as we pass by.

13 November 2013

Andrea Veri: Configuring DNSSEC on your personal domain

Today I ll be working out how to properly configure DNSSEC on a BIND9 installation, I ll also make sure to give you all the needed instructions to properly verify if a specific domain is being correctly covered by DNSSEC itself. In addition to that a few more details will be provided about adding the relevant SSHFP s entries on your DNS zone files to be able to automatically verify the authenticity of your domain when connecting to it with SSH avoiding any possible MITM attack. First of all, let s create the Zone Signing Key (ZSK) which is the key that will be responsible to sign any other record on the zone file which is not a DNSKEY record itself:
dnssec-keygen -a RSASHA1 -b 1024 -n ZONE gnome.org

Note: the dnssec-keygen binary file should be part of bind97 (RHEL 5) or bind (RHEL6) package according to yum whatprovides: RHEL 5:
32:bind97-9.7.0-17.P2.el5_9.2.x86_64 : The Berkeley Internet Name Domain (BIND) DNS (Domain Name System) server Repo : rhel-x86_64-server-5 Matched from: Filename : /usr/sbin/dnssec-keygen

RHEL 6:
32:bind-9.8.2-0.17.rc1.el6.3.x86_64 : The Berkeley Internet Name Domain (BIND) DNS (Domain Name System) server Repo : rhel-x86_64-server-6 Matched from: Filename : /usr/sbin/dnssec-keygen

Then, create the Key Signing Key (KSK), which will be used to sign all the DNSKEY records:
dnssec-keygen -a RSASHA1 -b 2048 -n ZONE -f KSK gnome.org

Creating the above keys can take several minutes, when done copy the public keys to the zone file this way:
cat Kgnome.org*.key >> gnome.org

When done you can clean out the useless bits from the zone file and just leave the DNSKEY records (which are not commented out as you will notice) An additional and cleaner way of accomplishing the above is to use the INCLUDE rule on the zone file itself as follows:
$INCLUDE /srv/dnssec-keys/Kgnome.org+005+12345.key $INCLUDE /srv/dnssec-keys/Kgnome.org+005+67890.key

Choosing which method to use is really up to you. Once that is done you can go ahead and sign the zone file. As of myself I m making use of the do-domain script taken from the Fedora Infrastructure Team s repositories. If you are going to use it yourself, make sure to adjust all the relevant variables to match your setup, especially keyspath, region_zones, template_zone, signed_zones and AREA. The do-domain script also checks your zone file through named-checkzone before signing it.
/me while editing the do-domains script with the preview of gnome-code-assistance!
If instead you don t want to use the script above, you can sign the zone file manually in the following way:
dnssec-signzone -K /path/to/your/dnssec/keys -e +3024000 -N INCREMENT gnome.org

By default, the above command will append .signed to the file name, you can modify that behaviour by appending the -f flag to the dnssec-signzone call. The -N INCREMENT will increment the serial number automatically making use of the RFC 1982 arithmetics while the -e flag will extend the zone signature end date from the default 30 days to 35. (this way we can safely run a monthly cron job that will sign the zone file automatically) You can make use of the following script to achieve the above:
#!/bin/sh SIGNZONE="/usr/sbin/dnssec-signzone" DNSSEC_KEYS="/srv/dnssec-keys" NAMEDCHROOT="/var/named/chroot" ZONEFILES="gnome.org" cd $NAMEDCHROOT for ZONE in $ZONEFILES; do $SIGNZONE -K $DNSSEC_KEYS -e +3024000 -f $ZONE.signed -N INCREMENT $ZONE done /sbin/service named reload

Once the zone file has been signed just make sure to include it on named.conf and restart named:
zone "gnome.org" file "gnome.org.signed"; ;

When you re done with that we should be moving ahead adding a DS record for our domain at our domain registrar. My example is taken from the known gandi.net registrar.
Gandi s DNSSEC interface
Select KSK (257) and (RSA/SHA-1) on the dropdown list and paste your public key on the box. You will find the public key you need on one of the Kgnome.org*.key files, you should look for the DNSKEY 257 entry as dig DNSKEY gnome.org shows:
;; ANSWER SECTION: gnome.org. 888 IN DNSKEY 257 3 5 AwEAAbRD7AymDFuKc2iXta7HXZMleMkUMwjOZTsn4f75ZUp0of8TJdlU DtFtqifEBnFcGJU5r+ZVvkBKQ0qDTTjayL54Nz56XGGoIBj6XxbG8Es+ VbZCg0RsetDk5EsxLst0egrvOXga27jbsJ+7Me3D5Xp1bkBnQMrXEXQ9 C43QfO2KUWJVljo1Bii3fTfnHSLRUsbRn8Puz+orK71qxs3G9mgGR6rm n91brkpfmHKr3S9Rbxq8iDRWDPiCaWkI7qfASdFk4TLV0gSVlA3OxyW9 TCkPZStZ5r/WRW2jhUY/kjHERQd4qX5dHAuYrjJSV99P6FfCFXoJ3ty5 s3fl1RZaTo8=

Once that is done you should have a fully covered DNSSEC domain, you can verify that this way:
dig . DNSKEY grep -Ev '^($ ;)' > root.keys dig +sigchase +trusted-key=./root.keys gnome.org. A cat -n

The result:
105 ;; WE HAVE MATERIAL, WE NOW DO VALIDATION 106 ;; VERIFYING DS RRset for org. with DNSKEY:59085: success 107 ;; OK We found DNSKEY (or more) to validate the RRset 108 ;; Ok, find a Trusted Key in the DNSKEY RRset: 19036 109 ;; VERIFYING DNSKEY RRset for . with DNSKEY:19036: success 110 111 ;; Ok this DNSKEY is a Trusted Key, DNSSEC validation is ok: SUCCESS

Bonus content: Adding SSHFP entries for your domain and verifying them You can retrieve the SSHFP entries for a specific host with the following command:
ssh-keygen -r $(hostname --fqdn) -f /etc/ssh/ssh_host_rsa_key.pub

When retrieved just add the SSHFP entry on the zone file for your domain and verify it:
ssh -oVerifyHostKeyDNS=yes -v subdomain.gnome.org

Or directly add the above parameter into your /etc/ssh/ssh_config file this way:
VerifyHostKeyDNS=yes

And run ssh -v subdomain.gnome.org , the result you should receive:
debug1: Server host key: RSA 00:39:fd:1a:a4:2c:6b:28:b8:2e:95:31:c2:90:72:03 debug1: found 1 secure fingerprints in DNS debug1: matching host key fingerprint found in DNS debug1: ssh_rsa_verify: signature correct

That s it! Enjoy!

Joachim Breitner: Constructing a list in a Monad

In Haskell, lists are ubiquitous. In real-world Haskell, monads are ubiquitous. So it should be an easy task to fill a list with values obtained in a monad, i.e. a list of n random numbers (in the Rand monad), or getting some input from the user, and storing it in a list, until the user chooses to finish the input. The task For now, assume a function getInput :: IO Int; we want to run it 10000 and then have the list of the values returned. Sounds simple and straight forward, but it is actually really hard to get the run-time behaviour that we naively and optimistically expect. The expectation In an imperative setting, we would have a simple counting loop. In the loop, we run getInput, allocate a new cell for the linked list, and append it to the list. Clearly, this

consumes no stack space and

at the end of the loop, the list is already fully evaluated in memory, ready to be used.

Can we achieve that with Haskell? Let s look at a few alternatives (complete code available)
Attempt 1: The accumulator I ll start with the probably worst attempt. Unfortunately, from what I have seen from correcting Haskell exams, this is what beginners would write, especially if they have the above imperative algorithm in mind, and know about the convert loops to recursion with accumulators approach to solving Haskell problems:
accumAppend :: Int -> IO [Int] accumAppend n = go n [] where go 0 l = return l go n l = do x <- getInput; go (n-1) (l++[x])
To check the space usage of this, I pass -Kn to the GHC runtime and see what limit is just enough to let this program calculate accumAppend 10000 and fully evaluate the resulting list. It turns out that we need 328336 bytes of stack space. So what about the second requirement; that the list is fully evaluated? Experienced Haskellers see it immediatelly: The accumulator is not used in the loop, so each iteration adds a thunk around the previous value, that would add the next entry to the end. Only when the list is actually used, these are run, each traversing the whole list, causing quadratic cost. We can verify this using ghc-vis:

Clearly (and not surprisingly) this is not the best solution. Attempt 2: The accumulator (forced) Lets try to fix the second issue, by making sure that the list is always fully evaluated. We import Control.DeepSeq and write
accumAppendSeq :: Int -> IO [Int] accumAppendSeq n = go n [] where go 0 l = return l go n l = do x <- getInput ; go (n-1) $!! (l++[x])
As the accumulator gets fully evaluated before being passed to the next invocation of go, the result will not contain thunks. But note that this has also fixed the stack consumption: The code now runs the smallest setting for -K, 8 bytes. This works as both go and deepseq are tail-recursive. But this is still not the solution we are looking for, as the quadradic cost caused by using ++ is still there. Attempt 3: The accumulator (reversed) Since we know that l++[x] is expensive, but x:l is cheap, we can simply use this to update the accumulator. This has the slightly annoying consequence that the entries of the list are in the reverse order, but we can fix that in the base case:
accumReverse :: Int -> IO [Int] accumReverse n = go n [] where go 0 l = return (reverse l) go n l = do x <- getInput ; go (n-1) (x:l)
And indeed, we get noticably faster code that still runs in 8 bytes of stack. Unfortunately, we still don t construct the final list directly. Attempt 4: Naive recursion Maybe we can do without an accumulator. The most naive such code would be
listRecurse :: Int -> IO [Int] listRecurse n = go n where go 0 = return [] go n = do x <- getInput; r <- go (n-1); return (x:r)
and I d expect that most experienced Haskellers would write that code (if they are asked not to use a library function). And indeed, this code does create the final list directly. But it requires a large stack or 164616 bytes. The reason is that this is no longer tail recursive: After calling go again we need to take the result and prepend x Attempt 5: library functions Maybe we should simply not worry about the implementation, and use library functions? Clearly, the authors of such libraries have found the best solution. So how does
listReplicateM :: Int -> IO [Int] listReplicateM n = Control.Monad.replicateM n getInput
fare? Unfortunately, not better than the naive recursion. In fact, the stack space requirement is the same 164616 bytes. The same holds when using special libraries for generating and consuming list, e.g. the Streams module from the vector package:
listStreams :: Int -> IO [Int] listStreams n = MStream.toList $ MStream.replicateM n getInput
Attempt 6: Difference lists It is time to dig deeper into our box of tricks. What if we have lists with constant time Snoc (a.k.a. appending a new element)? Then Attempt 3 would not require reversing the list. Such lists are provided by difference lists; there are libraries for that, but we can simply implement them using lambdas:
accumDList :: Int -> IO [Int] accumDList n = go n id where go 0 l = return (l []) go n l = do x <- getInput; go (n-1) (l . (x:))
Indeed, no stack is required (8 bytes are enough). But we are cheating here: We are still not constructing the final list, but rather we combine functions that append elements to lists. So when accumDList returns, what we have in memory, is a thunk and sequence of partial function applications in the wrong order, and evaluating the thunk does basically the same thing as reverse in Attempt 3. It might be a bit faster, is still not satisfying enough:

Attempt 7: Unsafe functions Even deepter in the box of tricks, somewhere in the grit and dust where one usually should not reach, there is a function that can help us out here: unsafeInterleaveIO. This allow us to modify the naive recursion in a way that first creates the Cons-cell, and then continues the loop:
listUnsafeInterleave :: Int -> IO [Int] listUnsafeInterleave n = do l <- go n; return $!! l where go 0 = return [] go n = do x <- getInput r <- unsafeInterleaveIO (go (n-1)) return (x:r)
The stack consumption is 8 bytes. It is worth noting that the all to deepseq (in $!!) will actually drive the evaluation of go. Also, it guarantees that the unsafe effects of unsafeInterleaveIO are confined to the execution of listUnsafeInterleave, i.e. are actually safe. Run time statistics I ran criterion over the functions (generating lists of length 1000), and found these results:

accumAppend: 6.5 ms

accumAppendSeq: 8.2 ms

accumReverse: 14.0 us

listRecurse: 8.0 us (same as listReplicateM and listStreams)

accumDList: 12.0 us

listUnsafeInterleave: 174.0 us

Conclusion There are many ways to write a list-constructing list in Haskell, none are perfect they either fill the heap, or do not construct the list directly (usually requiring a second pass through it), or rely on IO-specific unsafe functions. The naive recursion performs the best, but may cause a stack overflow (note, though that from GHC 7.8, the stack will be unlimited). The next best option seems to be the difference lists
I m still wondering: What would be required from Haskell, GHC or the monads in question to have a fully satisfactory solution here, i.e. one that is as fast as the naive recursion, as stack efficient as the difference list solution, and allocates no thunks, only list cells?

11 November 2013

Vincent Bernat: Snimpy: SNMP & Python

While quite old fashioned, SNMP is still an ubiquitous protocol supported by most network equipments. It comes handy to expose various metrics, like network interface counters, to be gathered for the purpose of monitoring. It can also be used to retrieve and modify equipments configuration. Variables exposed by SNMP agents (servers) are organized inside a Management Information Base (MIB) which is a hierarchical database¹. Each entry is identified by an OID. Querying a specific OID allows a manager (client) to get the value of an associated variable. For example, one common MIB-module is IF-MIB defined in RFC 2863. It contains objects used to manage network interfaces. One of them is ifTable whose rows are representing agent s logical network interfaces. Each row will expose the interface name, characteristics and various associated counters.

ifIndex ifDescr ifPhysAddress ifOperStatus ifOutOctets

1 lo up 545721741

2 eth0 0:18:f3:3:4e:4 up 78875421

3 eth1 0:18:f3:3:4e:5 down 0

ifTable is indexed by its first column ifIndex. If you want to get the operational status of the second interface, you need to query IF-MIB::ifOperStatus.2 which is translated to OID .1.3.6.1.2.1.2.2.1.8.2 using information provided by the MIB definition.
Scripting SNMP An SNMP agent can deliver a lot of interesting information:

interface counters with IF-MIB,

IP addresses with IP-MIB,

routing tables with IP-FORWARD-MIB,

inventory with ENTITY-MIB,

neighbors with LLDP-MIB.

You can gather those information manually with tools like snmpget and snmpwalk:
$ snmpwalk -v 2c -c public localhost IF-MIB::ifDescr IF-MIB::ifDescr.1 = STRING: lo IF-MIB::ifDescr.2 = STRING: eth0 IF-MIB::ifDescr.3 = STRING: eth1
However, building robust scripts with them is quite challenging. For example, if you wanted to get the descriptions of all active interfaces as well as the total number of octets transmitted, you could do something like that:
#!/bin/sh set -e host="$ 1:-localhost " community="$ 2:-public " args="-v2c -c $community $host" for idx in $(snmpwalk -Ov -OQ $args IF-MIB::ifIndex); do descr=$(snmpget -Ov -OQ $args IF-MIB::ifDescr.$idx) oper=$(snmpget -Ov -OQ $args IF-MIB::ifOperStatus.$idx) in=$(snmpget -Ov -OQ $args IF-MIB::ifInOctets.$idx) out=$(snmpget -Ov -OQ $args IF-MIB::ifOutOctets.$idx) [ x"$descr" != x"lo" ] continue [ x"$oper" = x"up" ] continue echo $descr $in $out done
Hopefully, SNMP bindings in various languages are pretty common. For example, Net-SNMP ships with a Python binding:
import argparse import netsnmp parser = argparse.ArgumentParser() parser.add_argument("host", default="localhost", nargs="?", help="Agent to retrieve variables from") parser.add_argument("community", default="public", nargs="?", help="Community to query the agent") options = parser.parse_args() args = "Version": 2, "DestHost": options.host, "Community": options.community for idx in netsnmp.snmpwalk(netsnmp.Varbind("IF-MIB::ifIndex"), **args): descr, oper, cin, cout = netsnmp.snmpget( netsnmp.Varbind("IF-MIB::ifDescr", idx), netsnmp.Varbind("IF-MIB::ifOperStatus", idx), netsnmp.Varbind("IF-MIB::ifInOctets", idx), netsnmp.Varbind("IF-MIB::ifOutOctets", idx), **args) assert(descr is not None and cin is not None and cout is not None) # if descr == "lo": continue if oper != "1": # continue print(" ".format(descr, cin, cout))
This binding is quite primitive and has several drawbacks:

It exports everything as strings. See .

Error handling is just deficient. If you mispell something, like a variable name, you ll get snmp_build: unknown failure on the standard error. No exception. If a variable does not exist, you ll get None instead. See .

This inability to sanely handle failures makes this binding quite dangerous to use in scripts. Imagine making important modifications on the basis of the returned values. If you forget to check against None, your script may cause havoc!
Snimpy Because I didn t find any reliable Python binding for SNMP, I decided to write Snimpy with two goals in mind:

Leverage information contained in MIBs to provide a pythonic interface.

Any error condition should raise an exception.

Here is how the previous script could be written:
#!/usr/bin/env snimpy import argparse parser = argparse.ArgumentParser() parser.add_argument("host", default="localhost", nargs="?", help="Agent to retrieve variables from") parser.add_argument("community", default="public", nargs="?", help="Community to query the agent") options = parser.parse_args() m = M(options.host, options.community, 2) load("IF-MIB") for idx in m.ifDescr: if m.ifDescr[idx] == "lo": continue if m.ifOperStatus[idx] != "up": continue print(" ".format(m.ifDescr[idx], m.ifInOctets[idx], m.ifOutOctets[idx]))
You can also use a list comprehension:
load("IF-MIB") print("\n".join([ " ".format(m.ifDescr[idx], m.ifInOctets[idx], m.ifOutOctets[idx]) for idx in m.ifDescr if m.ifDescr[idx] != "lo" and m.ifOperStatus[idx] == "up" ]))
Here is another simple example to get the routing database from the agent:
load("IP-FORWARD-MIB") m=M("localhost", "public", 2) routes = m.ipCidrRouteNextHop for x in routes: net, netmask, tos, src = x print(" :>15s / :<15s via :<15s src :<15s ".format( net, netmask, routes[x], src))
IP-FORWARD-MIB::ipCidrRouteNextHop is a more complex table with a compound index. Despite this, querying the table still seems natural. Have a look at Snimpy s documentation for more information. Behind the hood, SNMP requests are handled by PySNMP and MIB parsing is done with libsmi². Snimpy supports both Python 2, Python 3 and Pypy.

A MIB is defined using a subset of ASN.1 called SMI. However, it is not uncommon to refer to the definition as a MIB too.

Unfortunately, there is currently no robust SMI parser written in pure Python. For example, PySNMP relies on smidump which comes with libsmi. Snimpy uses a custom CFFI wrapper around libsmi.

10 November 2013

Sylvain Le Gall: opam2debian, a tool to create Debian binary package out of OPAM

One week ago, a thread in opam-devel mailing list started about the possibility to create binary snapshot to distribute OPAM packages. Distributing binary packages with everything already compiled is pretty useful when you want to make sure that everyone has the same version of packages installed and you don't want to spend time configuring all the computer of your colleague. As a matter of fact I was also interested to see that happening. I have several computers where I want to install a set of packages and I want to snapshot OPAM archives when I am ready for an upgrade. I have tested for a long time another source distribution: GODI. I even wrote a puppet module to drive it. This was a fun experience, but as with any source only distribution, there are some drawbacks. Especially even if it is fully automated, you get a lot of errors and timeout when trying to build automatically from source. This is how opam2debian has started. I wanted a replacement for puppet-godi that takes advantage of OPAM and the possibility to distribute my set of packages everywhere quickly. The goals of this project are:

generate a Debian binary package with all the dependencies set on external packages (like libpcre)

use OPAM to build everything

use standard Debian process to build package

create snapshot of OPAM repository that allow to rebuild exactly the same thing on different arches

The real challenge behind opam2debian was to be able to use standard Debian process to create package to get all the power of dependencies computation provided by the Debian maintainer scripts. My great achievement on this topic was to find a tool called proot that allows you to bind mount a directory as a user. This is an achievement because it allows to create a package using a directory where you are not allowed to write (i.e. /opt/opam2debian directory which is owned by root). This is a way to do it on any Jenkins builder without root access and a standard way for Debian to build packages. Usage example I need to compile a set of package to install on all my Jenkins builder. Here is the list of packages I need and I also want to use the latest OCaml version. I want to build a Debian package for Debian Wheezy which has only OCaml 3.12.1. Building the package:
$ opam2debian create --build --name opam2debian-test2 --compiler 4.01.0 \ ocamlfind fileutils ocaml-data-notation ocaml-expect ounit \ ocamlmod ocamlify oasis yojson sexplib extlib pcre-ocaml \ calendar ocaml-inifiles ocamlnet ocurl gettext inotify ocaml-sqlexpr \ ocamlrss ocaml-xdg-basedir
Getting the package list right can be tricky because the process will stop at the first error -- and if it is because the last package fails to build it can be long. I have implemented a --keep-build-dir in case you want to tune the package list live. The program will build everything and it can takes quite a while. At the end you get a file opam2debian-test2_20131105_amd64.deb which has a reasonable size of 232MB. That is big, but it looks like the biggest directory is $OPAMROOT/4.01.0/build, I am not sure if I can remove it but we may save some space here (the build directory represents 50% of the package size). Then you can just do a standard Debian installation:
$ sudo dpkg -i opam2debian-test2_20131105_amd64.deb
And you can use it:
$ eval $(opam config env --root /opt/opam2debian/opam2debian-test2/) $ which ocamlfind /opt/opam2debian/opam2debian-test2/4.01.0/bin/ocamlfind $ ocamlfind list [...] stdlib (version: [distributed with Ocaml]) str (version: [distributed with Ocaml]) threads (version: [distributed with Ocaml]) threads.posix (version: [internal]) threads.vm (version: [internal]) type_conv (version: 109.41.00) unidiff (version: 0.0.2) unix (version: [distributed with Ocaml]) userconf (version: 0.3.1) xdg-basedir (version: 0.0.3) xmlm (version: 1.1.1) yojson (version: 1.1.5)
A nice thing to note, is that it is a standard OPAM install. You can install, update and upgrade OPAM from there, as root. However, I would recommend not to do it, and just rebuild a newer Debian package to upgrade. Install You will need the opam and proot Debian package available in Debian jessie and sid. You will also need various OCaml libraries (cmdliner, calendar, fileutils and jingoo). Download the opam2debian tarball on the forge, build and install it. The project is hosted on github. Open issues On the initial list of goals of the project. Not everything is completed. I have still several open issues. In particular 4. (create snapshot of OPAM repository) was blocked by a bug in opam-mk-repo, that prevents snapshots (see my pull-request to solve it). Another issues is about licenses of the included files. I should list them all and I need to figure out a way to extract every licences. Submit bugs directly to github.

Luke Faraone: Why I use my bank's mobile site on my desktop

(or, cutting out bloat by using a platform where bloat won't fly)

Let me start off by saying I'm generally a huge fan of my bank, USAA. Their offerings are free of hidden fees, their phone support excellent, and the perks they provide are competitive. They don't have the best savings interest rates, but you can always find a better deal online to park money not actively in your checking account.

However, USAA's website is a behemoth. My account page took about 8 seconds to fully load, downloading 1.4MiB of content.

The "My Accounts" page you're redirected to after logging in.
It is frequently buggy; whenever I log in via Google Chrome on Ubuntu 12.04 I land on a page with a URL beginning with "https://www.usaa.com/inet/gas_bank/AccountBannerAjax" and a bunch of GET parameters like "currentaccountkey" and "accnumber" with values like "encrypted12a1f4dd1[ ]". The server returns a 200 OK, promises a Content-Length of 20, but then actually returns zero bytes. After navigating to the homepage and clicking a button, I end up getting logged in, but I wonder what percentage of their userbase are experiencing this problem?

For some strange reason, I get a lot of checks. It appears that nobody else informed the banking system that it's 2013, and the easiest mechanism for people to send money without paying fees is still on paper. To its credit, USAA made remote deposit of checks available to all customers in 2006, when it was mostly an offering limited to businesses. However, it seems like they haven't updated their web workflow since then.

Using it on the web still requires using a signed Java applet (itself discouraged by CMU's CERT) that does the incredibly complex task of letting you select a file from your computer and upload it to their servers. At least, that's what I think it does, because any time I chose "Run", my browser complained a few minutes later that the tab had stopped responding. Regardless of functionality, you can accomplish almost anything their site could currently be doing with HTML5 and a third party service if they want to crop images locally.

Spinning after logging
in on Android
USAA's mobile app for Android has another host of problems; I haven't been able to log into it for 2 weeks, and when I chatted with someone today I was told they were "doing some maintenance this weekend", so I should try again in a few hours once that's finished.

I googled around a bit for some way to perhaps make the applet work in Ubuntu (which admittedly is not a supported platform), and came upon a Facebook thread where a rep suggested using the mobile web site.

A breath of fresh air
I loaded it in my browser, and was amazed at how well it functioned. Obviously designed for higher-end devices (It didn't even load in one WAP emulator I tried), the mobile web interface was a refreshing breath of fresh air. It scaled well to a full-screen device (see below), loaded quickly, and gave me all the information I would have wanted out of the normal web interface.

Most notably: remember the whole "upload a check" workflow that required a buggy Java applet on the main website? We get bog-standard HTML form fields, no additional magic. There goes any theories about the Java client doing some magic validation or prep of the image; here, all they're getting is the images and my session cookie.

I'm still shocked at whoever thought a My Yahoo!-style homepage was the best layout for a bank, but props to the web developers who managed to make a mobile interface that was both pretty and allowed me to work around broken functionality in their implementations on every other platform I had access to.

But why was the mobile web interface the least bloated? Easy. On the desktop, you generally have a nice pipe, or if not, the user knows it and won't be too upset if your site is just as slow as other sites similarly situated. On mobile, the user downloaded all the code already, so the only latency should be the API requests against the server, right?

On the mobile web users have come to expect relatively speedy mobile-optimised sites and there's less screen real estate to do fancy things that get in the way of content. For many sites, that's a huge improvement. Of course, it would be really nice if more banks supported open protocols for interactions (USAA has a read-only, limited-duration OFX feed), but I would settle for a better web interface.

So tl;dr: USAA, please make www.usaa.com redirect to m.usaa.com, kthxbai.

Next.

Previous.

Search Results: "beh"

10 December 2013

Kees Cook: live patching the kernel

Russ Allbery: krb5-sync 3.0

8 December 2013

John Goerzen: Results with btrfs and zfs

5 December 2013

Daniel Kahn Gillmor: The legal utility of deniability in secure chat

28 November 2013

Debian Med: Bits from Debian Med team (by Andreas Tille)

27 November 2013

Steinar H. Gunderson: Stockfish

Timo Jyrinki: Workaround for setting Full RGB when Intel driver's Automatic setting does not work

23 November 2013

Mike Hommey: Don t trust python s os.execv

22 November 2013

Vincent Sanders: Error analysis is the sweet spot for improvement

20 November 2013

Matt Zimmerman: Scaling Human Systems: Management

19 November 2013

Carl Chenet: Yarn: a scenario testing tool

Francois Marier: Things that work well with Tor

Instant messaging Communication via XMPP is another use case that's not affected much by a bit of extra latency. To get Pidgin to talk to an XMPP server over Tor, simply open "Tools Preferences" and set a `SOCKS5` (not `Tor/Privacy`) proxy of `localhost` on port `9050`.

GMail Finally, I found that since I am running GMail in a separate browser profile, I can take advantage of GMail's excellent caching and preloading and run the whole thing over Tor by setting that entire browser profile to run its traffic through the Tor SOCKS proxy on port `9050`.

16 November 2013

Lars Wirzenius: Debian: developing it wrong

Russ Allbery: Review: Blue Remembered Earth

14 November 2013

Steve Kemp: Meanwhile, behind the facade of this innocent book store

13 November 2013

Andrea Veri: Configuring DNSSEC on your personal domain

Joachim Breitner: Constructing a list in a Monad

11 November 2013

Vincent Bernat: Snimpy: SNMP & Python

10 November 2013

Sylvain Le Gall: opam2debian, a tool to create Debian binary package out of OPAM

Luke Faraone: Why I use my bank's mobile site on my desktop

Series:	Poseidon's Children #1
Publisher:	Ace
Copyright:	January 2012
Printing:	June 2012
ISBN:	0-441-02071-2
Format:	Hardcover
Pages:	505

ifIndex	ifDescr	ifPhysAddress	ifOperStatus	ifOutOctets
1	lo		up	545721741
2	eth0	0:18:f3:3:4e:4	up	78875421
3	eth1	0:18:f3:3:4e:5	down	0

Search Results: "beh"

10 December 2013

8 December 2013

5 December 2013

28 November 2013

27 November 2013

23 November 2013

22 November 2013

20 November 2013

19 November 2013

Instant messaging Communication via XMPP is another use case that's not affected much by a bit of extra latency. To get Pidgin to talk to an XMPP server over Tor, simply open "Tools Preferences" and set a SOCKS5 (not Tor/Privacy) proxy of localhost on port 9050.

GMail Finally, I found that since I am running GMail in a separate browser profile, I can take advantage of GMail's excellent caching and preloading and run the whole thing over Tor by setting that entire browser profile to run its traffic through the Tor SOCKS proxy on port 9050.

16 November 2013

14 November 2013

13 November 2013

11 November 2013

10 November 2013

Instant messaging Communication via XMPP is another use case that's not affected much by a bit of extra latency. To get Pidgin to talk to an XMPP server over Tor, simply open "Tools Preferences" and set a `SOCKS5` (not `Tor/Privacy`) proxy of `localhost` on port `9050`.

GMail Finally, I found that since I am running GMail in a separate browser profile, I can take advantage of GMail's excellent caching and preloading and run the whole thing over Tor by setting that entire browser profile to run its traffic through the Tor SOCKS proxy on port `9050`.