Workshop: Security Token

Der Open Source Arbeitskreis (OSAK) der Fachschaft FSMPI, veranstaltet nun zum zweiten Mal eine Crypto Party auf der sich Interessierte über Verschlüsselung und verwandte Themen informieren können.

Ich möchte hier die Gelegenheit nutzen um etwas Werbung für diese Veranstaltung zu machen. Genaue Infos findet Ihr unten im Flyer.

Dieses Mal wird es auch einen kleinen Workshop von mir geben:

Hardware Crypto Tokens

„I know none of my passwords“

Ich werde in ca. 20 Min eine kurze Übersicht über Security Tokens wie bspw. den Yubikey oder die OpenPGP Smartcard geben. Dabei wird der Fokus auf verschiedenen Anwendungsszenarien wie bspw. One-Time-Passwords, Logins, E-Mail Verschlüsselung usw liegen.

Update: Hier sind die Vortragsfolien und das Handout:

Präsentation (pdf)
Handout (pdf)

cryptoparty-ss2015

Seminar: Camera-based PCB Analysis for Solder Paste Dispensing

2013-12-02_20.02.29

The lectures during my last semester were largely focused on digital image processing. Combining this with the inspiration for 3D printing, I gathered through my trip though South Korea, resulted in the following seminar paper. Seminars are a compulsory part of our curriculum which I like due the self-contained work and the ability to pick an individual topic.

Over the past year, I’ve built my own Kossel 3D printer. The Mini Kossel is based on a novel parallel delta kinematic which was developed by Johann C. Rocholl, a Google engineer from Germany.

This paper is targeting the automation of solder paste dispensing onto printed circuit boards by using computer vision and RepRap robots.

Full Slides as PDF
Full Paper as PDF
Source Code at GitHub

Seminar: Image Processing and Content Analysis

Camera-based PCB Analysis for Solder Paste Dispensing

Steffen Vogel (steffen.vogel@rwth-aachen.de)
Academic Advisor: Wei Li (wei.li@lfb.rwth-aachen.de)
Institute of Imaging & Computer Vision (LfB)
Rheinisch-Westfälische Technische Hochschule (RWTH), 52056 Aachen

1 Abstract

Two of the main challenges for PCB prototyping are the time-consuming setup of involved machines and their economic feasibility for small laboratories and hobbyists. This paper tries to offer solutions for both of these issues:

  1. The complex setup process of industrial machines can be accelerated by computer vision. It is preferable to automate this process as far as possible to enable the operation by untrained personnel and hobbyists. The workflow can be further simplified by not relying on external CAD data. This includes: detection of components, pads and footprints; mapping between available components and footprints and planning of shortest tool paths.
  2. The adaption of proven 3D printers allows to lower the costs for such machines. The lightweight and fast kinematics of parallel 3D-delta robots like the RepRap Mini Kossel are perfectly suited for the assembly of PCBs. Only the print head has to be exchanged between the individual steps of the process.

This work presents a workflow to control DIY 3D printers for the purpose of PCB assembly. By using cheap and easy-obtainable parts like proven RepRap 3D printers, this technique is viable for small laboratories, FabLabs and hobbyists. During the seminar, a analysis and control software for RepRap printers was written. Hence, we focus on the overall workflow and tools and less on algorithms and theory.
Here, the task of solder paste dispensing was chosen to be explored in detail. This work establishes the groundwork for more complex task like the pick and placing of electronic components.

2 Motivation

The ongoing miniaturization of electronic products like smartphones and Ultra Books has led to a new form factor for electronic components. Surface-mounted devices (SMD) are already widespread in electronic design and production. As a result, previously used through-hole components are gradually phased out. This miniaturization of SMD components is an ongoing trend and raises the barrier for hobbyists to produce PCBs themselves. Soldering and placement of 0401-sized resistors or BGA packages is not possible by hand any longer.

This work is motivated by the vision to build an all-in-one machine for the complete process of prototype PCB assembly (PCBA). To accelerate the development process and to reduce the costs, all of these tasks can be handled by a single workbench 3D printer / CNC mill. The PCB production process roughly can consists of the following steps:

  1. Isolation milling or pen plotting of PCB traces
  2. Drilling of holes and contours
  3. Solder paste dispensing for SMD pads with a syringe
  4. Pick-and-place of SMT components with vacuum
  5. Soldering with hot air, a hot plate or by a laser

For the scope of this paper, the process of solder paste dispensing was chosen. This task offers the biggest margin to profit from computer vision. Industrial mass production uses stencils to apply solder paste onto the PCB. For small prototype assemblies the fabrication of stencils is not worthwhile. Therefore, solder paste is applied manually with a pressurized syringe, which is hold by hand.
The dispensing of solder paste requires the knowledge exact solder pad positions and dimensions. Traditionally, this information is exported by CAD design tools and is required to produce the stencils.
But sometimes the CAD data is not available or stored in an inaccessible proprietary format. This paper presents techniques to gather the pad locations and dimensions by means of computer vision.

Fig. 1: Solder paste dispensing techniques
Fig. 1: Solder paste dispensing techniques
smd0805
Fig. 2: 0805-sized resistor
Seminar: Camera-based PCB Analysis for Solder Paste Dispensing weiterlesen

Thesis: Extended Abstract

Almost fourteen months ago, I started working on my bachelor thesis. Although I finished it half a year ago, it’s still part of my work as a student research assistant.

During my initial work, most of the code was written for an internal research kernel. I’m now happy that we were able to port it to an open source kernel called eduOS. This minimal operating system is used for practical demo’s and assignments during the OS course at my university. There’s much more I could write about. So this will probably be another separate blog post.

The motive for this article is an abstract I wrote for the student research competition of the ASPLOS conference which is held this year in Istanbul, Turkey. Unfortunately my submission got rejected. But as a nice side-effect, I’ve now the chance to present my work to an english audience as well:

PDF Version


Self-referencing Page Tables for the x86-Architecture

A simple Paging Implementation for a minimalistic Operating System

Steffen Vogel

Academic advisor: Dr. rer nat. Stefan Lankes
Institute for Automation of Complex Power Systems
E.ON Energy Research Center, RWTH Aachen University
Mathieustr. 10, 52074 Aachen, Germany

This was a submission for ASPLOS Student Research Competition ’15 Istanbul, Turkey1

ABSTRACT

The adoption of 64 bit architectures went along with an extension of the virtual address space (VAS). To cope with this growth, the memory management unit (MMU) had to be extended as well. For paging-based systems like Intel’s x86-architecture this was realized by adding more levels of indirection to the page table walk.

This walk translates virtual pages to physical page frames (PF) by performing look-ups in a radix / prefix tree in which every node represents a page table (Figure 1a). Since the tables are part of the translation process, they must be referenced by physical page frame numbers (PFN, blue line). As the operating system is only eligible to access the VAS, it cannot follow the path of a walk. In order to allow the manipulation of page tables, it must provide:

Page table walk in the x86 64 longmode: Traditional, without self-reference.
Figure 1a): Page table walk in the x86 64 longmode without self-reference.
  • Access to the table entries, by mapping the tables themselves to the VAS.
  • A mapping between physical references to corresponding locations in the VAS.

Additionally, every level of the page table walk increases the complexity of managing these mappings. They also increase the memory consumption by occupying physical page frames. It is possible to avoid both drawbacks by the technique described in the following.

In my bachelor thesis, I presented an approach, which is compatible with both the 32 bit and 64 bit version of Intel’s x86-architecture. This allows for a replacement of two code bases, one for each architecture, by one supporting both. Thus, results in a shorter, easier comprehensible, and maintainable code. As foundation for this implementation our teaching OS called “eduOS” was used2. “eduOS” supports only the 32 bit protected mode whereas the 64 bit longmode is only implemented for an internal research kernel.

Thanks to the sophisticated design of Intel’s x86 MMU, it is possible to avoid most of the complexity and space requirements by using a little trick. Adding a self-reference in the root table (PML4 resp. PGD) automatically enables access to all page tables from the VAS without the need for manual mappings as described above (Figure 1b). The operating system does not need to manually follow the path of a page table walk, as this task is executed by the MMU for accessing individual tables instead of page frames.

Page table walk in the x86 64 longmode: With self-reference.
Figure 1b): Page table walk with self-reference.

An access to the VAS region covered by a self-reference causes the MMU to look up the root table twice (red line). Effectively, this shifts the whole page table walk by one level. Therefore, it stops with the PFN of page tables instead of page frames that are usually translated by the MMU. Here, both the PML4 and PDPT indexes are used to choose an entry out of the PML4 table. Therefore, it must be guaranteed that PML4 entries can be interpreted as PDPT entries, too. This demands for the following requirements:

  • Homogenous coding of paging flags across all paging levels.
  • Equal table sizes across all paging levels.

Fortunately, the x86-architecture complies with this prerequisites as shown in Figure 2. Green colored flags are coded consistently across all paging levels. Only PAT, size and global flags have a slightly different meaning for entries in the PGT. My bachelor thesis shows that these deviations still allow maintaining full control caching and memory protection properties of self-mapped tables. This includes for common system calls like fork() and kill().

Similar flags across all paging levels.
Figure 2: Similar flags across all paging levels.

By repeatedly addressing the self-reference, it is also possible to access tables of the upper levels (PGD to PML4). Table 1 shows the resulting virtual addresses of all page tables when using the last (512th) entry of the PML4 table for the self-reference3. This grants access to all possible page tables, including those which might not yet exist and may be allocated in the future. Hence, the self-reference reserves a fixed fraction of the VAS for the page tables. The size of this region is equal to 256 TiB / 512 = 512 GiB for 64 bit (resp. 4 GiB / 1024 = 4 MiB for 32 bit), which is negligible in comparison to the huge VAS of 248 byte.

Virtual addresses of self-mapped tables.
Table 1: Virtual addresses of self-mapped tables.

For the manipulation of page table entries two approaches
are feasible:

  • Top-down Use known tree traversals, starting at the root node,
    which corresponds to the PML4 respectively PGD.
  • Bottom-up Use the page fault handler to create new tables on-the-fly,
    when they are not yet present.

But there are also other architectures which satisfy the prerequisites described above. One of these is the Alpha4 architecture, which suggests a similar approach in the reference manual. Intel and AMD do not mention the technique in their x86 manuals. In the field of operating systems, support is far more limited. There is only a single reference5 dated to 2010 indicating that Microsoft might use a similar approach for its NT kernel. Linux cannot profit because its paging implementation must support a broad selection of virtual memory architectures of which not all fulfill the requirements mentioned above.

Abschluss Bachelorarbeit

Nachdem ich vor knapp acht Monaten mit meiner Bachelorarbeit begonnen habe, freue ich mich nun diese fertigstellen zu können. Dazu lade ich alle Interessenten zu meiner Abschlusspräsentation ein:

am 18. Juni 2014
um 13:00 Uhr
im Raum BSZ-20 des EON Energy Research Center

Update: Nachdem ich am Mittwoch meine Arbeit mit der Bestnote abschließen konnte, möchte ich sie nun hier veröffentlichen:

Jetzt mag sich der Ein oder Andere wundern weshalb mein Vortrag im EON Energy Research Center (EONERC) und nicht im Lehrstuhl für Betriebssysteme (LfBS) stattfindet. Der Lehrstuhl für Betriebssysteme wurde von unserer Fakultät aufgelöst. Die wissenschaftlichen Mitarbeiter setzen Ihre Arbeit nun in anderen Instituten fort.

EON Energy Research Center

Abschluss Bachelorarbeit weiterlesen

Thesis

Seit fast zwei Monaten schreibe ich jetzt am Lehrstuhl für Betriebssysteme meine Bachelorarbeit:

Eine generische Speicherverwaltung mit Hilfe von Seitentabellen für ein
minimalistisches Betriebssystem

oder auf Englisch

A generic memory management with paging for a minimalistic operating
system

Huh?! Was ist das? Was machst du da?“ Da dies häufig die erste Reaktion von Freunden und Familie ist, möchte ich versuchen das Thema meiner Arbeit hier kurz und verständlich vorzustellen. Wer Interesse an einem tieferem Verständnis und technischen Details hat, lade ich gerne zu meinem Abschlussvortrag Ende Mai ein. Zu dem „Was machst du da?“ kann ich schon einmal sagen, dass ich viel am Programmieren bin und dabei unheimlich viel praktische Erfahrung sammele. Und es nen riesen Spaß macht 😀

Meine Arbeit dreht sich also um Betriebssysteme. Die Aufgabe von Betriebssystemen ist es verfügbare Ressourcen zu verwalten und diese mit einer einheitlichen Schnittstelle dem Nutzer zu Verfügung zu stellen. In meinem Fall arbeite ich an der Verwaltung des Arbeitsspeichers.
Arbeitsspeicher (engl. RAM für Random Access Memory) findet man in Handys, TVs, MP3 Playern, Laptops und vor allem in Server und Hochleistungsrechnern. Es ist einer recht schneller dafür auch leicht flüchtiger Speicher, den man gut mit dem menschlichen Kurzeitgedächtnis vergleichen kann. „Random Access“ steht für einen wahlfreien Zugriff, also dass man alle Informtionen ohne vorheriges „Spulen“ oder „Nadel umsetzen“ abfragen kann – um mal in nostalgischen Analogien zu sprechen.

quote-Bill-Gates-640k-ought-to-be-enough-for-anybody-89027

Dieses Zitat, das gerne dem Microsoft Gründer Bill Gates zugeschrieben wird, dürfte vielleicht einigen von euch bekannt sein. Waren im Jahr 1981 noch 640 KB das Maß der Dinge haben heutige Server 64 GB und mehr. Dies entspricht verblüffend genau einer Verdopplung der Kapazität alle zwei Jahre wie es Gordon Moore bereits schon 1965 postuliert hat.

Aber nun mal wieder zurück zu meiner Arbeit: diese rasante Entwicklung der Speicherkapazität hat Betriebssysteme vor einigen Jahre vor wesentliche Probleme gestellt.
Stellen wir uns vor – ähnlich wie die Größe des Speichers, hätte sich die Anzahl der Autohalter in Deutschland entwickelt. Den Zulassungsstellen wären recht schnell die Nummernschilder ausgegangen, da es einfach nicht genügend unterschiedliche Kombinationen von Landkreis und Buchstaben/Zahlen gäbe. Und wer möchte schon das gleiche Nummernschild wie sein Nachbar haben. Jedes Auto muss also eindeutig identifizierbar und jeder Speicherplatz eindeutig adressierbar sein. Mit zunehmender Anzahl an Autohaltern, bzw. der Speicherkapazität, steigt daher auch Komplexität der Verwaltung.

In meinem Beispiel könnte man dieses Problem beispielsweise durch einen zusätzlichen Buchstaben für das Bundesland auf jedem Nummernschild lösen. Man denke an die Einführung der EU-Kennzeichen.
Und damit bin ich auch schon beim Ziel meiner Arbeit: Ich möchte dieses Verwaltungsproblem für beliebe große Speicherkapazitäten und beliebig viele Verwaltungsinstanzen lösen ohne die Kompexität dadurch zu steigern.

Puh, das soll erst einmal reichen. Ende Mai werde ich diese, meine erste wissenschaftliche, Arbeit abschließen. So lange behalte ich meine Lösung noch für mich :p