Category Archives: Uncategorized

Neues Skript zum Vorkurs, v4.5

Eine neue Version des Skripts zum Vorkurs “formale Methoden der Informatik”ist hier verfügbar.

In Version 4.5 hat sich geändert:
Weitere Beispiele zur vollständigen Induktion hinzugefügt.
Kapitel 7.1: wesentlich mehr Beispiele für Relationen hinzugefügt.

In Version 4.4 hat sich geändert:
Hinweis auf Einschreibtermine hinzugefügt.
Kapitel 3.6: Motivation zum “Umdrehen” der Quantoren hinzugefügt.
Kapitel 6.2: Beweise zur Partialsumme der geometrischen Reihe und zu x · x = x + x hinzugefügt.

Vorkurs “formale Methoden der Informatik” im WS 2017/18

Das Institut für Informatik der Universität Bonn bietet dieses Jahr wieder den Vorkurs “formale Methoden der Informatik” an, den ich wieder halten werde, jetzt bereits im vierten Jahr.

Der Vorkurs wird angeboten für frische Erstsemester in Informatik und gibt einen Überblick über das Wissen, was von den Studenten erwartet wird und einen Ausblick, was im ersten Semester an Stoff noch kommen wird. Er ist freiwillig und unbenotet.

Ich kann allen neuen Studenten den Vorkurs nur ans Herz legen, da sie einen schnellen und einfachen Überblick über den Stoff erhalten, der dann später im Semester noch einmal in Tiefe behaltelt wird. Und Sie lernen schon etwas vor dem Semster Ihre Kommilitonen und den Betrieb der Universität kennen.

Interessenten melden sich bitte im precampus-System an.

Der Vorkurs findet statt von Montag, 18.9.2017 bis Freitag, 29.9.2017, jeden Tag von 10-12 Uhr im Hörsaal 2, Institut für Informatik, Römerstr. 164, Bonn.

Weiterhin finden jeden Tag Übungen dazu statt, von 12-14 Uhr. Allen Studenten sei angeraten, zu den Übungen zu gehen, auch wenn der Stoff vielleicht einfach erscheint. In den Übungen besteht Gelegenheit, Fragen zu stellen, es werden Aufgaben zur Vorlesung gerechnet und man kann die neuen Kommilitonen kennenlernen. Es werden keine Hausaufgaben gestellt.

Es gibt ein Skript, welches hier verfügbar ist (Version 4.0 vom 12.9.2017). Da es auch während des Vorkurses Updates geben wird, drucken Sie besser immer nur Teile aus—falls Sie es überhaupt ausdrucken!  Ich werde hier immer die neueste Version des Skripts anbieten. Ich bin sehr interessiert daran, Fehler im Skript zu korrigieren: bitte sprechen Sie mich in oder nach der Vorlesung an oder auch online.

Vorkurs “Formale Methoden der Informatik” im WS 2016/17

Ich halte auch im WS 2016/17 wieder den Vorkurs “Formale Methoden der Informatik” an der Universität Bonn. Der Vorkurs wendet sich an Studierende, die jetzt im Wintersemester ihr Studium der Informatik beginnen.

Der Vorkurs ist freiwillig und unbenotet, aber eine Anmeldung ist hier erforderlich.

Der Vorkurs findet statt von Montag, 26.9.2016 bis Freitag, 7.10.2016, jeden Tag von 10-12 Uhr im Hörsaal 2, Institut für Informatik, Römerstr. 164, Bonn. Am 3.10. (Feiertag) fällt der Kurs ersatzlos aus.

Weiterhin finden jeden Tag Übungen dazu statt, von 12-14 Uhr. Wir raten Ihnen, zu den Übungen zu gehen, auch wenn Sie denken, dass Sie das alles schon voll drauf haben. 😉 In den Übungen haben Sie Gelegenheit, Fragen zu stellen, es werden Aufgaben zur Vorlesung gerechnet und Sie lernen Ihre neuen Kommilitonen kennen. Es gibt keine Hausaufgaben.

Es gibt ein Skript, welches hier verfügbar ist (Version 3.2 vom 7.10.2016). Da es auch während des Vorkurses Updates geben wird, drucken Sie besser immer nur Teile aus, falls Sie es überhaupt ausdrucken. 🙂 Ich werde hier immer die neueste Version des Skripts anbieten. Ich bin sehr interessiert daran, Fehler im Skript zu korrigieren: bitte sprechen Sie mich in oder nach der Vorlesung an oder auch online.

Getting a kernel mode driver signed for Windows 10

In this article I want to describe my experiences with the new (as of August 2016) driver signing issues and Windows 10.

Since the Anniversary Update of Windows 10 (version 1607, also called Redstone1), Microsoft requires new signatures on your kernel mode drivers under certain circumstances. This is called “attestation signing”. That is to say, only if certain circumstances are met — and I guess these “loopholes” will get smaller over the years — you can run drivers that were signed the “old” way (called “cross-certification”) on Windows 10.

The “new” way brings certain big changes:

  • The “old” way meant you — as the software developer — use your certificate to sign your software. Since your certificate is cross-signed by a certification authority (CA) that is (in the end) trusted by Microsoft this ensures that no one could tamper with the file and that Microsoft trusts that you are who you claim you are.
  • The “new” way means that you submit your software to Microsoft and they add their certificate, provided all the requirements are met.
  • For that, you need an EV code signing certificate, there is no way around it. This basically means, it’s more expensive and it comes on an USB hardware token (so you cannot copy it).

To give an idea of what has to be done, I describe what I did. My company, cFos Software GmbH, needs cFosSpeed, our traffic shaping driver signed for Windows 10.

Getting an EV certificate

I got the certificate from Globalsign Germany, as I always did, just this time I ordered the “extended verification” (EV) certificate. This increased the price from 429€ (about $480 as of 2016-09-02) for 3 years to 709€ (about $793)! (Note to self: in next life, run a certification authority!)

The process is kinda smooth, they require some (updated) documents (HRB printout), check that the provided contact data (email address and phone number) is correct and have you sign the agreement. They were very helpful and the whole process required some three days plus another two until I got the USB token by mail. If this is your first time you order a certificate from a CA, it might take longer, since they must check more data.

On that USB token you have to download the certificate from their website. You can do that only once, so there is no easy way to share the same certificate with several people (two teams in two offices, for example). You cannot just copy the USB token, of course.

The actual signing works as always, only now a password box pops up every time you sign. Luckily, copy-and-paste works for the password entry.

On the plus side, Microsoft SmartScreen instantly trusts files that where signed with an EV certificate. So that might ease out the roll-out of new software a bit.

Here is what Microsoft says about getting a code signing certificate.

Getting the Microsoft Signature

Prerequisites

It’s harder as I imagined (of course). Firstly, you need a Microsoft sysdev account. I don’t recall how I created that, but I gather it wasn’t that hard.

Secondly, you need to download some file (called winqual.exe)  from Microsoft (under Administration / manage certificates), sign it with your EV certificate and upload it again. This way, you only prove that your company has an EV certificate. That same certificate has to be used later to sign your submission.

Thirdly, you need to “sign” some legal documents. “Sign” luckily only means typing your name and the date and it’s almost instantly countersigned. They don’t say which documents need signing beforehand, so I guessed we might need “Windows Compatibility Program and Driver Quality Attestment Testing Agreement” and signed it. But that wasn’t enough, so I signed “Windows Certification Program Testing Agreement v1.0” as well, which seemed to be almost the same. After that, I was able to proceed further.

Submitting

Now I was able to upload our driver for signing. There are two ways of submitting:

  • Using the Hardware Lab Kit (HLK) to test your submission against Windows 10 and use the Hardware Certification Kit (HCK) to test against earlier versions of Windows. Merge the results and upload that to Microsoft.
  • Cross-sign the drivers yourself and upload to Microsoft for attestation signing. That is what I did. Microsoft mentions that drivers signed this way won’t run on Windows Server 2016 Technical Preview.

Firstly, I sign the files myself in the usual way using signtool.exe:

signtool sign /a /ac GlobalSign_Root_CA.crt /s my /n “Company name” /fd sha256 /td sha256 /tr “http://timestamp.globalsign.com/?signature=sha2” /du “http://www.example.com” cabfilename.cab

You need the “sha256” options, since SHA1 has been deprecated since 2016-01-01 and will work less and less in the future. Make sure that you use the same certificate you used to sign winqual.exe earlier on.

Secondly, you need to put the .SYS driver file and its .INF file into one .CAB archive into a subdirectory. Here is a description from Microsoft on how to actually pack the files and sign them by yourself. Note, that I used CABARC instead of MAKECAB to pack the files:

md driver
copy driver.sys driver.inf driver
cabarc -p -r N cabfilename.cab driver\*

I chose to include our .CAT file as well, even though the submission process will create one for you. I don’t know yet if that was a good or bad choice, both ways seem to work.

Thirdly, sign that .CAB file like you signed the .SYS file (see above).

Forthly, I uploaded that signed .CAB archive to sysdev.microsoft.com. You will have to choose for which versions of Windows 10 your driver qualifies. I checked all versions, but only one architecture (x64 or x86). You can only have one architecture per submission!

… and waiting

The submission takes a while and goes through a ten step process, namely:

  1. (no idea)
  2. Transferring CAB File
  3. Scanning CAB file for Viruses
  4. Decompressing CAB File
  5. Validating HCK/HLK Submission Package
  6. Creating Catalog Files
  7. Archiving Files
  8. Parsing Driver Data
  9. Signing Catalog Files
  10. Transferring Catalog File to Server

OSR describes in this post that the whole process took them 30 Minutes. But the first time I submitted, step 5 took six days and hadn’t completed! Then I wrote an email to sysdev@microsoft.com to find out that I had built my .CAB file the wrong way (I had put all files into the root folder instead of a “driver” sub-folder) and that had apparantly hung the process. (Thanks again for a timely and succinct answer, Jack!) So If you have to wait for long period of time, it’s probably best to contact Microsoft by mail and solve the issue.

Fixing that problem and re-submitting the driver package got me an approved driver within 10 minutes! 🙂 🙂

Victory!

After that you can download the signed .SYS and .CAT files packed into a .ZIP file. When you install that driver it doesn’t pop up that box asking “Do you trust Company X?” So, that’s nice.

What’s less nice is that drivers signed like this, even though they retain our old EV signature, don’t load under Windows 8.1 and load like they have no signature at all (and thus look kinda bogus, since they have no reference to the publisher) under Windows 7. So far, I have found no way to have a single driver file that loads under all Windows 7+ operating systems.

Resources

 

Vorkurs “Formale Methoden der Informatik” WS 2015/16

Ich halte in diesem WS 2015/16 wieder den Vorkurs “Formale Methoden der Informatik” an der Universität Bonn. Der Vorkurs ist gedacht für Studenten, die jetzt im Wintersemester ihr Studium der Informatik beginnen.

Der Vorkurs ist freiwillig und unbenotet, aber eine Anmeldung ist hier erforderlich.

Der Vorkurs findet statt von Montag, 28.9.2015 bis Freitag, 9.10.2015, jeden Tag von 10-12 Uhr (außer am 2.10. und 5.10.: 13-15 Uhr) im Hörsaal 2, Institut für Informatik, Römerstr. 164, Bonn.

Weiterhin finden jeden Tag Übungen dazu statt, von 13-15 Uhr (außer am 2.10. und 5.10.: 15-17 Uhr). Wir raten Ihnen zu den Übungen zu gehen, auch wenn Sie denken, dass Sie das alles voll drauf haben. 😉 In den Übungen haben Sie Gelegenheit, Fragen zu stellen und es werden Aufgaben zur Vorlesung gerechnet. Es gibt keine Hausaufgaben.

Ich habe ein Skript vorbereitet, welches hier verfügbar ist (Version 2.0.6). Da es auch während des Vorkurses Updates geben wird, drucken Sie besser immer nur Teile aus, wenn Sie es überhaupt ausdrucken. 🙂 Ich werde hier immer die neueste Version des Skript anbieten.

Update: der Vorkurs ist inzwischen vorbei, aber das Skript ist hier immer noch verfügbar. Hinweise sind weiterhin willkommen.

Slides and Links to my ISSAC ’15 Talk

I held my talk at ISSAC 2015 in Bath, UK on Wednesday July, 8th about “Implementation of the DKSS Algorithm for Multiplication of Large Numbers”. My paper is now available from the ACM digital library (or here locally) and the slides are available on the ISSAC website (or here locally).

To the ISSAC organizers and everyone present: the conference was awesome, thank you very much! I had a great time.

BibTeX for the paper:

@Conference{Lueders2015,
  Title                    = {Implementation of the DKSS Algorithm for Multiplication of Large Numbers},
  Author                   = {Christoph L{\"u}ders},
  Booktitle                = {ISSAC 2015 --- Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation},
  Year                     = {2015},
  Pages                    = {267--274},
  Abstract                 = {The Sch{\"o}nhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For N-bit numbers it has a time bound of $O(N \log N \log \log N)$. De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotically faster algorithm with a better time bound of $N \log N 2^{O(\log^* N)}$. For this paper, a simplified DKSS multiplication was implemented. Assuming a sensible upper limit on the input size, some required constants could be precomputed. This allowed to simplify the algorithm to save some complexity and run-time. Still, run-time is about 30 times larger than SSA, while memory requirements are about 2.3 times higher than SSA. A possible crossover point is estimated to be out of reach even if we utilized the whole universe for computer memory.},
  Doi                      = {10.1145/2755996.2756643}
}

Implementation of the DKSS Algorithm for Multiplication of Large Numbers — ISSAC’15

My paper “Implementation of the DKSS Algorithm for Multiplication of Large Numbers” was accepted for ISSAC’15 Conference to be held on 6-9 July 2015 at the University of Bath, U.K. !

Abstract: The Schönhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For \(N\)-bit numbers it has a time bound of \(O(N \cdot \log N \cdot \log \log N)\). De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotically faster algorithm with a better time bound of \(N \cdot \log N \cdot 2^{O(\log^∗ N)}\). For this paper, a simplified DKSS multiplication was implemented. Assuming a sensible upper limit on the input size, some required constants could be precomputed. This allowed to simplify the algorithm to save some complexity and run-time. Still, run-time is about 30 times larger than SSA, while memory requirements are about 2.3 times higher than SSA. A possible crossover point is estimated to be out of reach even if we utilized the whole universe for computer memory.

This is an improved version of what I wrote about in my diploma thesis.

My source code that was used for the tests is available here and is licensed under LGPL.