#index

index

este es el índice

sistemas operativos 1-systemes-dexploitation

algo 2-algorithmes

information security 3-securite-dinformation

cyber security 4-cyber-security

ordinateurs 5-computers

math 6-mathematics

#computation #ordinateurs #fr

Systèmes d'exploitation

C'est le programme ou ensemble de programmes qui gère l'utilisation des ressources d'un ordinateur par des logiciels applicatifs. On peut dire que le OS est l'interface entre le matériel et les applicatifs

Parties

• kernel ou noyau 1d-kernel
• services 1p-kernel-services
• drivers ou pilotes 1n-drivers
• user-land 1o-userland

exemples

• UNIX 1k-unix
• GNU/Linux 1e-gnu-linux
• MacOS 1f-macOS
• Android 1g-android
• Windows 1h-windows
• FreeDOS 1j-freedos

Concepts

• compilation 1a-compilation
• EFL format 1c2-format-ELF
• système des fichiers 1c-systeme-des-fichiers

#compilation #programmes #ordinateurs #fr

compilation

c'est le processus dont on utilise pour transformer un code source en un fichier binaire executable (appelé code objet).

Un des languages compilées le plus connue est C. Concrètement, le GNU C Compiler gcc (1a3-gcc), bien qu'il y en ait d'autres.

Par contre, il y a aussi des langages interprétées (1m-langages-interpretees).

Outils

puedes usar nm para inspeccionar la tabla de símbolos de un ejecutable ELF... si no has usado strip.

On peut utiliser 1a4-make pour automatiser la compilation de plusieurs fichiers.

#linux #unix #commands #fr

nm

De la manpage:

#computation #compilation #fr

code objet

C'est un ensemble des instructions normalement en code binaire.

#c #gcc #gnu #linux #ordinateurs #en

GNU C Compiler

It's the C compiler of the GNU project.

• storage class in the compiler 1a3a-gcc-storage-class

#c #gcc #gnu #linux #ordinateurs #en #keywords

gcc storage class

static1

1. variable: stores the variable statically allocated in memory instead of automatically. As a consequence, the variable will preserve its value between calls. See strtok implementation. See storage class. ²
2. function: The function will be visible only for functions from the same file. You can find lots of this folks at linux module programming.
3. arrays: set the minimum size of an array

   void setpasswd(char password[static 16]);
   

#compilation #programmes #ordinateurs #en #make

make

The make utility will determine automatically which pieces of a large program need to be recompiled, and issue the commands to recompile them.

make looks for instructions in a file named Makefile.

obj-m

The obj-m-thing¹

obj-m += nom.o

When the module is built from multiple sources, an additional line is needed listing the files:

<module_name>-y := <src1>.o <src2>.o ...

For detailed info about this you can refer here

#computation #ordinateurs #fr

Systèmes des fichiers

On utilise le terme pour designer l'organisation des informations de fichiers 1c1-fichier dans un dispositif de stockage, mais aussi utilisé pour designer l'organisation des fichiers (et repertoires) dans le système d'exploitation.

exemples des fichiers exécutables

• ELF 1c2-format-ELF
• Mach-O 1c3-format-Mach-O
• PE 1c4-format-PE

#informatics #computation #os

fichier

C'est un abstraction qui consiste en un ensemble d'octets encodant des informations. Les informations ont de sense a cause d'un format

• 1c2-format-ELF
• 1c3-format-Mach-O
• 1c4-format-PE
• 1c5-format-FAT

#unix #linux #ordinateurs #fr

formato ELF

C'est le format des binaires exécutables dans les systèmes UNIX.

#macos #ordinateurs #fr

Mach-O format

C'est le format de fichiers

#windows #ordinateurs

Portable Executable (PE)

Format de fichiers exécutables du système d'exploitation windows.

#windows #ordinateurs #fr

FAT

File Allocation Table. Créé initialement pour MS-DOS 1m-msdos.

#systemesdexploitation #kernel #ordinateurs #fr

kernel

C'est la partie du système d'exploitation qui gère les ressources de l'ordinateur et qui s'execute en mode système. Notamment, le noyau fournit des mécanismes d'abstraction de la mémoire, des processeurs et des périphériques.

Le kernel est aussi un programme et doit être codé, compilé et il est mappé dans la mémoire vive tant qu'on utilise le système d'exploitation. Pour des raisons de sécurité, l'adresse de base du kernel n'est pas fixée dans le mapping. 1d12-KASLR

Quand un programme ou application a besoin d'accès mémoire ou doit se communiquer avec un périphérique, il doit demander au kernel pour faire operation pour lui. C'est qu'on connais comme appel système (1l-syscall).

classement des noyaux 1d1-kernel-structure-types.

exemples

• linux 1d8-linux
• windows NT kernel 1d9-windows-nt-kernel
• XNU 1d10-xnu
• unix kernel 1d11-unix-kernel

#kernel #security #memorycorruption

kernel classement

Les noyaux peuvent être classifiés en fonction de leur structure et leur conception par rapport au système d'exploitation.

• noyau monolithiques 1d2-kernel-monolithique
• micro-noyau 1d3-micro-kernel
• noyau monolithique modulaire 1d4-kernel-monolithique-modulaire
• micro-noyau hybride 1d5-micro-kernel-hybride
• exokernel 1d6-exokernel
• unikernel 1d7-unikernel

#fr #kernel #todo

unix kernel

uni devices 1d11a-unix-drivers

#unix #kernel #drivers #fr

pilotes UNIX

Les dispositifs étaient identifiés par deux numéros: major et minor. major -> type de service minor -> instance du device

#kernel #informatics #computerscience #fr

Kernel monolithique

Compilé statiquement sur une seule binaire et il est chargé entièrement en mémoire. Ils sont généralement optimisés pour une architecture especifique. En consequence, on a bon performance, mais une grand surface d'attaque et portabilité limité.

exemples

• UNIX 1k-unix

#kernel #fr

micro-noyau

Le µ-noyau minimise les fonctionnalités intégrées au noyau en plaçant la plus grande partie des services du système d'exploitation à l’extérieur du noyau. C'est-à-dire, les services sont exécutés en mode S.

En consequence, la sécurité est renforcé, aussi que la souplesse et la portabilité. Par contre, on perde en performance à cause d'avoir besoin de basculer entre mode S et mode U. Aussi, on a besoin d'standardiser une API afin que les services interagissent avec le µ-noyau.

On appelle µ-noyau enrichi à l'ensemble logiciel formé par le µ-noyau et ses services.

#kernel #fr

Noyau monolithique modulaire

Les services du système d'exploitation se transforment en modules qui sont mis dedans le noyau dynamiquement. Les services sont exécutés en mode S une fois chargés et partagent le même space d'adressage que le coeur du noyau.

En tant que les modules sont exécutés en mode S, l'aspect sécurité peut être compromis.

exemples

• linux 1d8-linux

#kernel #fr #systemesdexploitation

micro-kernel hybride

C'est un µ-noyau qui intègre directement certains services cruciaux, mais le reste de services restants sont à l’extérieur du noyau.

#exokernel #kernel #fr

exokernel

micro-kernel minimum qui apporte accès au hardware sans imposer politiques d'haute niveau. Les applications ont plus de flexibilité au moment d'interagir avec le hardware mais, par contre, les applications peuvent être plus laborieuses à faire.

Par example: l'exokernel apporte accès secure au disque en évitant les accès non autorisés; et la manière dont l'information du disque est abstrait dépendra des applications ou la bibliothèque dont l'application en particulier est en train d'utiliser.

#unikernel #kernel #systemesdexploitation #fr

unikernel

C'est un noyau spécialisée pour une application ou une nombre très limité d'applications. Dans ce paradigme, tous les applications partage le même space d'adressage. On obtient une système d'exploitation qui a besoin de peu space et avec une surface d'attaque réduit. Attractifs pour microservices.

Tant les unikernels comme les exokernels appartiennent a la categorie des systèmes d'exploitation bibliothèque.

#kernel #linux #fr #todo #en

linux kernel

• linux kernel architecture 1d8h-linux-kernel-architeture
• linux file struct 1d8f-linux-file-struct
• linux drivers 1d8a-linux-drivers
• linux modules 1d8e-linux-modules
• development 1d8i-linux-kernel-development

#kernel #drivers #fr #sorbonne

pilotes dans linux

Les pilotes sont associés au dispositifs (devices) et on le traitera de manière indifférencié.

Les pilotes sont accessibles dans la partition devfs dans /dev/.

• character -> échange d'octets (char) 1d8b-linux-char-device
• block -> échange des bloques d'octets 1d8c-linux-block-devices
• network -> contrôle des périphériques réseau 1d8d-linux-network-device

L'identification des pilotes est fait comme dans UNIX: avec le major et minor 1d11a-unix-drivers.

Concevoir un pilote de périphérique 1d8a1-linux-drivers-programming

#kernel #programming #fr #drivers

Linux drivers programming

Guidelines

• Définir les services attendus
• Doit réutiliser le code des autres sous-systèmes.
• Le code doit être réentrant. Il faut éviter l'usage des variables globales dans les fonctions (voir strtok(...), par example).

Au niveau pratique, il y a beaucoup de similitudes entre écrire un driver et écrire un module.

• allocation des numéros major et minor1d8a2-linux-drivers-major-minor-allocation
• la structures file_operations 1d8a3-linux-drivers-file-operations

#kernel #programming #fr #drivers #fileops

Linux drivers programming

La structure file_operations est défini dans linux/fs.h est il a des champs qui sont des pointeurs aux fonctions. Chaque fichier char associé à un driver est associé a une structure file_operations 1d8f-linux-file-struct.

 struct file_operations {
	struct module *owner;
	loff_t (*llseek) (struct file *, loff_t, int);
	ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
	ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
	ssize_t (*read_iter) (struct kiocb *, struct iov_iter *);
	ssize_t (*write_iter) (struct kiocb *, struct iov_iter *);
	long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long);
	long (*compat_ioctl) (struct file *, unsigned int, unsigned long);
	int (*open) (struct inode *, struct file *);
	int (*release) (struct inode *, struct file *);
	/* ... */
}

#kernel #programming #fr #drivers #fileops #char

Linux char device programming

les fonctions

le décorateur __user indique que les pointeurs sont dans l'espace utilisateur. C'est-à-dire, il est possible qu'il soit pas disponible ni en RAM. Utilise les fonctions de asm/uaccess.h (1d8a3a1-linux-driver-uaccess) pour transférer la mémoire entre espace kernel et espace utilisateur.

Il est préférable d'implementer les fonctions en suivant certaines directives¹

• open 1d8a3b-linux-driver-char-device-open
• release (close) 1d8a3c-linux-driver-char-device-close
• read 1d8a3d-linux-driver-char-device-read
• write 1d8a3e-linux-driver-char-device-write

#kernel #programming #fr #drivers #fileops #char

linux - uaccess fonctions

This functions are in linux/uaccess.h

unsigned long copy_to_user(void __user *to, const void *from, 
						   unsigned long count);
unsigned long copy_from_user(void *to, const void __user *from, 
						     unsigned long count);

#kernel #programming #fr #drivers #fileops #char

linux char device - open

On doit performer le suivant:

• tester erreurs liées au dispositif specific.
• initialiser le dispositif si jamais il est la premiere fois qu'il est ouvert
• metre a jour le pointeur f_op, si nécessaire.
• faire l'allocation de la memoire à mettre dans filp->private_data, si nécessaire.

#kernel #programming #fr #drivers #fileops #char

linux char device - close

On doit performer le suivant:

• désallouer la mémoire, si nécessaire.
• éteindre le dispositif si jamais on est les derniers à l'utiliser.

#kernel #programming #fr #drivers #fileops #char

linux char device - read

ssize_t read(struct file *filp, char __user *buff, size_t count, loff_t *offp); 

• buff. cette variable pointe vers l'adresse mémoire où les données lues devraient être placées.
• count. c'est la taille de la donnée à transférer
• offp. indiques la position dont l'usager accede.

La valeur de retourne

interpreté pour les applications

• si elle est égale à count, donc le nombre de octets demandé ont été transmit.
• s elle est positive, mais plus petite que count, donc on se sont transmit qu'une partie des octets demandés.
• si elle est égale a 0, donc on a trouvé EOF mais on a rien lu
• si elle est négative, donc erreur. Regarde linux/errno.h 1d8g-linux-errno

#kernel #programming #fr #drivers #fileops #char

linux char device - write

ssize_t write(struct file *filp, const char __user *buff, size_t count, loff_t *offp);

• buff. cette variable pointe vers l'adresse mémoire celui des données qu'on va transférer au dispositif.
• count. c'est la taille de la donnée à transférer
• offp. indiques la position dont l'usager accede.

la valeur de retourne

• si elle est égale à count, donc le nombre de octets demandé ont été transmit.
• s elle est positive, mais plus petite que count, donc on se sont transmit qu'une partie des octets demandés.
• si elle est égale a 0, donc on a rien écrit.
• si elle est négative, donc erreur. Regarde linux/errno.h 1d8g-linux-errno

#linux #kernel #fr

linux character device

/dev/mem -> /dev/kmem

linux driver char device programming 1d8a3a-linux-drivers-char-device-programming

#linux #modules #kernel #fr #sorbonne

Linux modules

Les modules du linux ajoute des services dans le noyau: pilotes 1d8a-linux-drivers, appels systèmes, implementations des protocoles réseau.

Dans linux, il peut être chargé ou déchargé dynamiquement. Les modules s'execute en mode système.

cheat-sheet on linux module development here

Les modules linux doivent toujours avoir une fonction d'initialisation et une fonction de sortie:

/* headers here */

static int __init mod_init(void) { /* ... */ }

static void __exit mod_cleanup(void) { /* ... */ }

module_init(mod_init);
module_exit(mod_cleanup);

Module dependencies

If a module X uses at least one symbol from module Y, then X depends on Y. The dependencies are automatically inferred when compiled and available at /lib/module/<version>/module.dep generated by depmod.

Building a module

The running kernel is deployed with a generic Makefile ¹ 1a4-make

make -C /lib/module/\\((uname -r)/build M=\\)PWD

This following Makefile can be used to compile a kernel module:

KERNELDIR_LKP ?= /lib/modules/$(shell uname -r)/build

obj-m += helloWorld.o

all:
	make -C \\((KERNELDIR_LKP) M=\\)$PWD modules

clean:
	make -C \\((KERNELDIR_LKP) M=\\)$PWD clean

#kernel #linux #fr #todo #fileops #file

structure file

C'est la structure qui gère les fichiers ouverts dans le noyau linux.

struct file {
	struct list_head       f_list;        /* list of file objects */
	struct dentry          *f_dentry;     /* associated dentry object */
	struct vfsmount        *f_vfsmnt;     /* associated mounted fs */
	struct file_operations *f_op;         /* file operations table */
	atomic_t               f_count;       /* file object's usage count */
	unsigned int           f_flags;       /* flags specified on open */
	mode_t                 f_mode;        /* file access mode */
	loff_t                 f_pos;         /* file offset (file pointer) */
	struct fown_struct     f_owner;       /* owner data for signals */
	unsigned int           f_uid;         /* user's UID */
	unsigned int           f_gid;         /* user's GID */
	int                    f_error;       /* error code */
	struct file_ra_state   f_ra;          /* read-ahead state */
	unsigned long          f_version;     /* version number */
	void                   *f_security;   /* security module */
	void                   *private_data; /* tty driver hook */
	struct list_head       f_ep_links;    /* list of eventpoll links */
	spinlock_t             f_ep_lock;     /* eventpoll lock */
	struct address_space   *f_mapping;    /* page cache mapping */
};

#kernel #linux #fr #todo #en #sorbonne

Linux kernel architecture 1

Linux offers six main functions

• Process management 1d8h2-linux-process
• Memory management 1d8h3-linux-memory-management
• Network management
• Storage management
• System interface
• Human interface

through five abstraction layers:

1. User space interfaces

   System calls, procfs, sysfs, device files, …

2. Virtual subsystems 1d8h1-pseudo-file-systems

   Virtual memory, virtual filesystem, network protocols, …

3. Functional subsystems

   Filesystems, memory allocators, scheduler, …

4. Devices control

   Interrupts, generic drivers, block devices, …

5. Hardware interfaces

   Device drivers, architecture-specific code, …

#os #linux #sorbonne #en #kernel

Pseudo file systems

using pseudo file systems

the pseudo file system has to be enabled and mounted before being used

1. Check if the kernel has been build with the pseudo file system
2. mount the pseudo file system
3. have fun

in-memory file system 1d8h1a-ramfs

#pseudofilesystem #linux #kernel #en #sorbonne in-memory file system

ramfs (ram based file system) is a file system not backed by a storage device: stored completely in memory or computed when accessed.

Examples: procfs, sysfs, configfs, debugfs, devfs, tmpfs...

Proc: user apps can access the files of the ramfs with the posix API (read, write, seek,...)

Con: These mechanisms are synchronous from user to kernel, but asynchronous in the other direction, i.e., user space applications cannot be notified when the value represented by a file changes in memory.

ramfs representing the kernel data or conf

proc file system 1d8h1a1-procfs

sys file system 1d8h1a2-sysfs

config file system 1d8h1a3-configfs

debug file system 1d8h1a4-debugfs

#todo: ioctl ? read ? fileoperations ?

#kernel #proc #filesystem #ramfs

procfs

mounted in /proc. Meant to be used for export information about processes but used for exporting kernel data.

• pros: well documented
• cons: no real structure enforced There are two APIs:
• proc_fs API
  • legacy
  • files are limited to one page (PAGE_SIZE)
• seq_file API
  • allows larger data to be exported

Successor de procfs, mounted in /sys. Meant to store information about subsystems, hardware devices, drivers... This should be the default choice

Pros:

• Hierarchical topology
• Provides a set of mechanisms to free memory and recursively destroy directories Cons:
• complex
• each file represents one single piece of data
• a piece of data cannot be larger than one page (PAGE_SIZE)

directories 1d8h1a2a-sysfs-folders

files 1d8h1a2b-sysfs-files

diff: snprintf sprintf

#linux #sorbonne #kernel #sysfs

kobjects

One folder is associated to one struct kobject

struct kset {
	struct list_head list;
	spinlock_t list_lock;
	struct kobject kobj;
	const struct kset_uevent_ops *uevent_ops;
} __randomize_layout;

struct kobject {
	const char		*name;
	struct list_head	entry;
	struct kobject		*parent;
	struct kset		*kset;
	const struct kobj_type	*ktype;
	struct kernfs_node	*sd; /* sysfs directory entry */
	struct kref		kref;

	unsigned int state_initialized:1;
	unsigned int state_in_sysfs:1;
	unsigned int state_add_uevent_sent:1;
	unsigned int state_remove_uevent_sent:1;
	unsigned int uevent_suppress:1;

#ifdef CONFIG_DEBUG_KOBJECT_RELEASE
	struct delayed_work	release;
#endif
};

Those are the parent kobject:

/* The global /sys/kernel/ kobject for people to chain off of */
extern struct kobject *kernel_kobj;
/* The global /sys/kernel/mm/ kobject for people to chain off of */
extern struct kobject *mm_kobj;
/* The global /sys/hypervisor/ kobject for people to chain off of */
extern struct kobject *hypervisor_kobj;
/* The global /sys/power/ kobject for people to chain off of */
extern struct kobject *power_kobj;
/* The global /sys/firmware/ kobject for people to chain off of */
extern struct kobject *firmware_kobj;

#kobject #sysfs #attributes #sorbonne #linux

struct attribute

each file in the sysfs corresponds to one single value and is associated to an instance of a struct kobj_attribute.

struct kobj_attribute {
	struct attribute attr;
	ssize_t (*show)(struct kobject *kobj, struct kobj_attribute *attr,
			char *buf);
	ssize_t (*store)(struct kobject *kobj, struct kobj_attribute *attr,
			 const char *buf, size_t count);
};

struct attribute {
	const char		*name;
	umode_t			mode;
#ifdef CONFIG_DEBUG_LOCK_ALLOC
	bool			ignore_lockdep:1;
	struct lock_class_key	*key;
	struct lock_class_key	skey;
#endif
};

kobjtect attributes can be created with the following macro:

#define __ATTR(_name, _mode, _show, _store)

Another macros

• __ATTR_RO for read-only attributes
• __ATTR_WO for write-only attributes
• __ATTR_RW for read/write attributes.

Operations

struct sysfs_ops {
	ssize_t	(*show)(struct kobject *, struct attribute *, char *);
	ssize_t	(*store)(struct kobject *, struct attribute *, const char *, size_t);
};

Parents

/* The global /sys/kernel/ kobject for people to chain off of */
extern struct kobject *kernel_kobj;
/* The global /sys/kernel/mm/ kobject for people to chain off of */
extern struct kobject *mm_kobj;
/* The global /sys/hypervisor/ kobject for people to chain off of */
extern struct kobject *hypervisor_kobj;
/* The global /sys/power/ kobject for people to chain off of */
extern struct kobject *power_kobj;
/* The global /sys/firmware/ kobject for people to chain off of */
extern struct kobject *firmware_kobj;

#pseudofilesystem #linux #kernel #en #sorbonne #configfs

configfs

mounted in /sys/kernel/config.

Pros

• allows user space programs to manage kernel objects Cons
• complex to set up
• one file equals one value

cgroups

#pseudofilesystem #linux #kernel #en #sorbonne #debugfs

debugfs

mountpoint: /sys/kernel/debug

Pros

• no size limit for files
• very high level and simple API Cons
• only for debugging purposes !

#tag #tagg

1d8h2-linux-process

PID

struct pid
{
	refcount_t count;
	unsigned int level;
	spinlock_t lock;
	struct dentry *stashed;
	u64 ino;
	/* lists of tasks that use this pid */
	struct hlist_head tasks[PIDTYPE_MAX];
	struct hlist_head inodes;
	/* wait queue for pidfd notifications */
	wait_queue_head_t wait_pidfd;
	struct rcu_head rcu;
	struct upid numbers[];
};

#kernel #linux #fr #todo #en #sorbonne #memory

Memory Management

Memory organisation

The smallest management unit is the page, even if the memory is byte addressable.

• a page (virtual page) is a fixed-size block of contiguous virtual memory.
• a page frame (physical page) is a fixed-size block of contiguous physical memory. The size depends on the architecture.

page frame -> cadre de page

Kernel representation of pages

The kernel maintains a struct page for each page frame available on the system.

struct page {
	unsigned long flags;		/* Atomic flags, some possibly
					 * updated asynchronously */
	union {
		struct {	/* Page cache and anonymous pages */
			union {
				struct list_head lru;
				/* Or, for the Unevictable "LRU list" slot */
				struct {
					/* Always even, to negate PageTail */
					void *__filler;
					/* Count page's or folio's mlocks */
					unsigned int mlock_count;
				};
				/* Or, free page */
				struct list_head buddy_list;
				struct list_head pcp_list;
			};
			/* See page-flags.h for PAGE_MAPPING_FLAGS */
			struct address_space *mapping;
			union {
				pgoff_t index;		/* Our offset within mapping. */
				unsigned long share;	/* share count for fsdax */
			};
			unsigned long private;
		};
		struct {	/* page_pool used by netstack */
			unsigned long pp_magic;
			struct page_pool *pp;
			unsigned long _pp_mapping_pad;
			unsigned long dma_addr;
			atomic_long_t pp_ref_count;
		};
		struct {	/* Tail pages of compound page */
			unsigned long compound_head;	/* Bit zero is set */
		};
		struct {	/* ZONE_DEVICE pages */
			struct dev_pagemap *pgmap;
			void *zone_device_data;
		};
		struct rcu_head rcu_head;
	};

	union {		/* This union is 4 bytes in size. */
		unsigned int page_type;
		atomic_t _mapcount;
	};
	/* Usage count. *DO NOT USE DIRECTLY*. See page_ref.h */
	atomic_t _refcount;

#ifdef CONFIG_MEMCG
	unsigned long memcg_data;
#elif defined(CONFIG_SLAB_OBJ_EXT)
	unsigned long _unused_slab_obj_exts;
#endif
#if defined(WANT_PAGE_VIRTUAL)
	void *virtual;			/* Kernel virtual address (NULL if
					   not kmapped, ie. highmem) */
#endif /* WANT_PAGE_VIRTUAL */
#ifdef LAST_CPUPID_NOT_IN_PAGE_FLAGS
	int _last_cpupid;
#endif
#ifdef CONFIG_KMSAN
	struct page *kmsan_shadow;
	struct page *kmsan_origin;
#endif
} _struct_page_alignment;

struct page is around 40 bytes. So we have 40 bytes for every 4Kib. You can increase the page size in order to reduce the metadata footprint

Zones

The kernel separates pages in multiple zones with different properties. But:

• some hardware can only do Direct Memory Accesses (DMA) to certain addresses.
• some architectures have a physical address space larger than their virtual address space, which means that some frames are not permanently mapped into the kernel address space.
• ZONE_DMA
• ZONE_DMA32
• ZONE_NORMAL
• ZONE_HIGHMEM

Memory API

internal fragmentation: when we store way less information than needed. external information: when we have blocks of free memory interspersed by allocated memory.

Buddy allocator

We have a page size of 4KiB and we allocate in "buddies" of powers-of-two contiguous pages.

Limitations: we can't allocate less than one page. If you ask for 513B, you'll get 1KiB allocated (external fragmentation).

slab layer

The slab layer create caches, each of which contains a certain type of objects, e.g, struct inode.

Each cache is then divided into slabs, blocks of contiguous memory that contain a certain number of instances of the object stored by this cache.

A slab contains the actual data and maintain their proper status (used or free). When the slab is full, the slab layer will allocate a new one.

NUMA: Non-uniform Memory Access.

SLAB Allocator

Frame layout

SLUB Allocator

Introduced in 2007. Locality by having per-cpu slabs, still NUMA aware.

Frame layout:

SLOB Allocator

Memory Pools

Used when you need a guarantee that memory will be available.

Creation / Destruction

/**
 * mempool_create - create a memory pool
 * @min_nr:    the minimum number of elements guaranteed to be
 *             allocated for this pool.
 * @alloc_fn:  user-defined element-allocation function.
 * @free_fn:   user-defined element-freeing function.
 * @pool_data: optional private data available to the user-defined functions.
 */
mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn, mempool_free_t *free_fn, void *pool_data);
void mempool_destroy(mempool_t *pool)

typedef void * (mempool_alloc_t)(gfp_t gfp_mask, void *pool_data);
typedef void (mempool_free_t)(void *element, void *pool_data);

Freeing memory

Reference counter

They keep track of the number of users using an object. Whenever the counter reaches 0, the object is not in use anymore and can be freed.

To use a reference counter, add a struct kref into your structure:

struct kref {
	refcount_t refcount;
};

void kref_get(struct kref *kref); // increments the kref


/**
 * kref_put - decrement refcount for object.
 * @kref: object.
 * @release: pointer to the function that will clean up the object when the
 *       last reference to the object is released.
 *       This pointer is required, and it is not acceptable to pass kfree
 *       in as this function.  If the caller does pass kfree to this
 *       function, you will be publicly mocked mercilessly by the kref
 *       maintainer, and anyone else who happens to notice it.  You have
 *       been warned.
 */
int kref_put(struct kref *kref, void (*release)(struct kref *kref));

#kernel #linux #fr #todo #en

Linux kernel development

Is important to keep in mind the directory tree

the kernel dynamic linker 1d8i1-kernel-dynamic-linker

Annotations

The __init and __exit annotations are used to help the compiler optimise the memory usage.
When some module is statically built-in the kernel binary, functions tagged with these annotations are placed in specific segments:

• .init.text that is freed after the boot of the kernel
• .exit.text that is never loaded in memory

#kernel #linux #fr #todo #en

Kernel dynamic linker

By default, module have access to no variable or function from the kernel, even if they are not static.

export symbols to modules

EXPORT_SYMBOL(s) // makes s visible to all loaded modules
EXPORT_SYMBOL_GPL(s) // makes s visible to all modules GPL-compatible licensed

You need to declare your symbol extern and load the module where it is defined.

#todo #gnu #gnulinux

GNU-Linux

Uses the linux kernel 1d8-linux

Démarrage

Etape 1: Firmware: BIOS / (U)EFI

• BIOS. code qui lance le bootloader

• MBR (Master Boot Recorder). table de description des partitions sur les disques

• Le BIOS charge le MBR

  • Bootstrap.
  • Va voir les quelques octets au début de la partition marqué comme bootable
  • chargeur de démarrage. LILO. GRUB
  • Très peu de place. Très peu de sécurité

• Les BIOS a des limitations

  • Il ne peut gérer des disques de plus de 2.3 To (Table de partition), 1Mo de RAM
  • Legacy mais encore utilisé pour IOT/Android
  • Entre 200 et 500 octets pour le bootloader dans le premier secteur du disque

• Couple: (U)EFI/GPT

• Gestion plus poussée par modules

• Ajout de la sécurité (signatures des modules EFI)

  • Utilisation des GUID Partition Table (max 8Zio)
  • Permet un boot sécurisé des MAJ sécurisés, un stockage des noyaux systèmes (utilisation de code signé)
  • Inclus la gestion réseau

• Chaque disque peut avoir sa partition EFI

  • ~100Mo à ~1Gio pour y stocker le bootloader
  • Formater en FAT32. Certains EFI support exFAT/NTFS ou autre

• La cohabitation est difficile

Sécurité uEFI

• Protection du bootloader. Pas forcement des noyaux
• Peut s'appliquer au boot par le réseau et périphériques externes Plataform key (PK)
• Stockée dans la variable EFI nommée PK.
• Format: x509 (clef publique dans certificat)
• Mise à jour: uniquement une nouvelle clef signée avec l'ancienne clef PK
• MAJ: directement dans l'interface physique EFI possible
  • en général protégé par mot de passe
  • en général suppression seulement
• Si on détruit la PK, on passe a mode config
• N'est pas utiliser pour signé des binaires
  • La plupart des ordinateurs viennent avec 2 clefs microsoft pré-installes KEY EXCHANGE KEY (KEK)
• Stockée dans KEK
• format: X509 OU RSA ...

The Signature Database (db)

• Stockée dans la variable db Machine Owner Key (MOK)

Etape 2: Exéction du BookLoader du BIOS

• charge une carte (map) du disque pour le système
• Charge le noyaux des OS (Linux, Windows, etc)
• Pour l'EFI ...

Etape 3 (optionnel)

• Si le noyaux contient tous les drivers nécessaire, initrd peut être ignoré
• ...

Etape 4: Exécution du noyau

Le bootloader exécute le noyau en transmettant les arguments

Etape 5: Création du premier processus

• init ou systemd en Linux

Etape 6: Interprétation des fichiers de configurations du system par les fils du processus 1

• Niveaux d'exécution (runlevel) -> /etc/inittab
  • 1. Utilisateur
  • 2. Multiutilisateur
  • 3
  • 4
  • 5
  • 6 /etc/rc.d/rc

/etc/init.d/

Etape 7:

Android OS

1g1-adroid-rooting

5b1a2-arm

#android #en

Adroid Rooting

1g1a-samsung-a12

content

#en #samsung #android #root #odin

Samsung A12

Galaxy A12 SM-A127M

One UI Core: 5.1 Android version: 13 Baseband version: A127MUBSEDXJ2 Kernel version: 4.19.111-27127798 Knox version: 3.9; API Level 36 Build number TPA1.220624.014.A127MUBSEDXJ2 DC9V; 1.67A

content

firmware

f6155d2540b5013774a77e846da5651c

f6155d2540b5013774a77e846da5651c SAMFW.COM_SM-A127M_PEO_A127MUBSEDXJ2_fac.zip

0152ccdedd545ccfd3ebb52005261ca2

#unix #systemesdexploitation #c #fr

Unix

Histoire

• 1969. Ken Thompson (ATT Bell labs) écrit la première version pour un PDP-7 de ce qui sera Unix
• 1970. Ken Thompson et Dennis Ritchie l’adaptent au DEC PDP-11/20. Au passage ils développent le premier compilateur C.
• 1979. ATT annonce son intention de créer une version commerciale d’Unix. En réaction l’université de Californie à Berkeley lance sa propre variante : BSD UNIX.
• 1990. La coopération entre Sun et ATT donne naissance à la System V R4 qui comporte de nouveaux standard d’unification d’UNIX. En réaction, les autres grands constructeurs, dont DEC, HP et IBM, décident de créer l’OSF (Open Software Foundation).
• 1991. La guerre des clones commence avec l’arrivée de Linux et FreeBSD.

#systemesdexploitation #kernel #ordinateurs #fr #syscall

appel système

C'est le mécanisme utilisé pour les applicatifs utilisateurs pour demander l'accès au ressources de l'ordinateurs au noyau.

#msdos #systemesdexploitation #fr

MS-DOS

#drivers #systemesdexploitation #fr

Pilote de périphérique noyau

On peut voir les pilotes de périphériques comme des extensions du noyau. Un périphérique est un composant matériel additional communicant avec l'ordinateur (mouse, clavier, haut-parleur, etc).

L'organisation et nature des pilotes peut varier entres systèmes d'exploitation différents. linux drivers 1d8a-linux-drivers unix drivers 1d11a-unix-drivers

#algorithmes #fr

algorithmes

Un algorithme c'est...

fonction d'hachage 2a-hash-function

algorithmes réparties 2b-distributed-algorithms

#hash #digest #infosec #fr #algorithmes

fonction d'hachage

C'est une fonction qui...

fonction d'hachage cryptographique 2a1-cryptographic-hash-function

#crypto #algorithmes #hash #fr

Fonction d'hachage cryptographic

C'est une fonction d'hachage qui a des propriétés particuliers:

• la taille de l'image est fixé (\(n\))
• elle est déterministe
• la probabilité d'un sortie est bas (~\(2^{-n}\))
• résistance à la préimage
• résistance à la deuxième préimage.
• résistance aux collisions

\[ x_1 = \frac{1}{0} \]

exemples

• md5
• bcrypt
• ntlm hash 2a1a-ntlm-hash-function

#crypto #hash #activedirectory #ntlm #fr

fonction d'hachage de NTLM

#algorithmes #fr #distributedalgorithms #sorbonne

Algorithmique repartie

Système réparti:

Ensemble interconnecté d'entités autonomes qui communiquent via un medium de communication -- G. Tel

Canaux de communication 2b2-communication-channels

Caractérisation d'un calcul réparti

• non séquentiel. deux instructions peuvent être exécutées simultanément.
• non centralisé. Les paramètres décrivant l'état du système sont répartis.
• non déterministe. deux actions concurrentes peuvent être exécutées dans n'importe quel ordre.

But d'un système réparti

• technique. mise en commun des ressources matérielles de plusieurs machines
  • Factorisation des coûts
  • Partage de charge
  • Tolerance aux pannes 2b3-failures
• fonctionnel. mise en commun d'information entre plusieurs utilisateurs en systèmes.
  • Travail coopératif entre utilisateurs
  • Automatisation de chaînes de traitement

Classification des applications répartis 2b1-distributed-apps-classification

Modèles temporelles 2b4-temporal-models

Critères d'evaluation 2b5-evaluation-criteria

Verification d'un algorithme réparti 2b6-distributed-algorithms-verification

Algorithmes à vagues 2b7-wave-algorithms

Exclusion mutuelle 2b8-distributed-mutex

Detection de la terminaison 2b9-termination-detection

P2P 2b10-peer-to-peer

table d'hachage distribuée 2b11-hash-table

#algorithmes #fr #distributedalgorithms #sorbonne

Classification des applications répartis

• processus coopérants. les processus interagissent via des mémoires ou des variables partagées.

gérer les conflits d’accès aux ressources communes.

• processus communicants. les processus s’échangent des messages par l'intermédiaire de canaux 2b2-communication-channels.

gérer l'échange de la connaissance.

#p2p #distributedalgorithms #activedirectory #sorbonne #en

Systèmes pair-à-pair

Napster

The first simple but successful P2P-application.

• File retrieval: the requesting peer contacts the peer having the file directly and downloads it

def. A p2p computer network is a network that relies primarily on the copmuting power and bandwidth of the participants in the network rather than concentrating it in a relatively small number

• Bootstrapping
• Service discovery
• Overlay structure maintenance
• Neighbour status tracking
• Application layer routing
• Resilience, handling link and node failures
• ...

Taxonomy of p2p-apps

P2P structured

P2P non-structured

#distributedalgorithms #hashtable #sorbonne

Hash Table

Principe table hachage

#algorithmes #fr #distributedalgorithms #sorbonne

Canaux de communication

• Risque de déséquencement des messages

canal FIFO = pas de déséquencement

• Risque de perte de messages

communications fiables

• Certains canaux peuvent avoir une capacité bornée.

Topologies de systèmes répartis 2b2a-distributed-topologies

#algorithmes #fr #distributedalgorithms #sorbonne

Topologies de systèmes répartis

Topologie logique

La manière dont la communication entre sites est organisée (structure de contrôle)

• Representation sous forme de graphe
  • sommets -> processus (ou nœuds)
  • arêtes -> canaux (ou lien) de communication
• Caractéristiques du graphe
  • connexes -> chaque paire de nœuds est reliée par un chemin
  • fortement connexe (graphe orienté) -> il existe un chemin entre chaque paire de nœuds en respectant le sens des arcs
  • incomplet -> tous les processus ne communiquent pas deux à deux directement
• Paramétrés définis sur le graphe
  • distance entre deux nœuds -> longueur du plus court chemin entre ces deux nœuds
  • diamètre du graphe -> la plus longue des distances entre deux nœuds du graphe
  • degré d'un nœud -> nombre de voisins du nœud.

Topologie physique

"câblage" du réseau. Sur un topologie physique connexe quelconque, on peut toujours implanter une structure de contrôle en arbre.

Topologies particulières

• anneau bidirectionnel
• étoile
• clique (graphe complet)
• hypercube

#algorithmes #fr #distributedalgorithms #failures #sorbonne

Fautes en systèmes repartis

Composantes impactés

• processus
• machines
• canaux de communication

Origines des fautes:

• logiciels (de conception ou programmation)
  • quasi-déterministes. très difficiles à traiter à l'execution
• matérielles (ou plus généralement système)
  • non-déterministes. transitoires
  • corrigées par point de reprise ou masquées par réplication
• piratage 4a-cyber-attaques
  • affecte durablement un sous ensemble de machines
  • masqué par réplication

Classification des fautes 2b3a-failure-classification

#algorithmes #fr #distributedalgorithms #failures

Classification des fautes

• faute franche. arrêt définitif du composant.
• faute d'omission. un résultat en un message n'est transitoirement pas délivré.
• faute temporelle. un résultat ou un message est délivré trop tard ou trop tôt.
• faute byzantine. inclut tous les types de fautes, y compris le fait de délivrer un résultat ou un message erroné (intentionnellement au nom).

#algorithmes #fr #distributedalgorithms #sorbonne

Modèles temporelles

• Constat
  • vitesses des processus différents.
  • délais de transmissions variables
• Problème.
  • combien de temps attendre avant de reprendre au déclarer l’échec
• Démarche.
  • élaborer des modèles temporelles pour lesquels on puisse tirer des propriétés.

Problèmes du consensus 2b4a-consensus-problem

Horloges 2b4b-clocks

#algorithmes #fr #distributedalgorithms #sorbonne #clock

Horloges

On considere un système réparti comme un ensemble de processus asynchrones s’exécutant sur différents sites. Les proc communiquent uniquement par message. Il y a pas d'horloge globale.

Types d'événements

• événements locaux. changement de l'état interne d'un processus. e_i
• emissions de messages send(m)
• receptions de messages recv(m)
• délivrance de messages delivre(m)

On veut pouvoir tracer l'execution et donner une relation de causalité entre événements.

Datation 2b4b5-datation

Horloges physiques

• Problème. ils dérivent au cours de temps et le sens et l'amplitude de la dérive est propre à chaque machine.
• Consequence: la précédence causale n'est pas respectée. 2b4b1-causal-order

Horloges logiques

def.

\(H\): ensemble des événements de l'application (muni de l'ordre partiel \(\rightarrow\))

\(T\): domaine de temps (muni de l'ordre partiel \(<\)). \[ \begin{align} C: &H \longrightarrow T \\ &e\longmapsto C(e) \text{ tq } e\rightarrow e' \Rightarrow C(e) < C(e') \end{align} \] on dit que l'horloge capture la causalité.

Si, en plus, \(C(e) < C(e') \Rightarrow e \rightarrow e'\) (consistence forte), on dit que l'horloge caractérise la causalité.

• horloges scalaires 2b4b2-lamport-timestamps
• horloges vectoriels 2b4b3-vector-clock
• horloges matricielles 2b4b4-matrix-clock

#algorithmes #fr #distributedalgorithms #sorbonne #clock

Relation de précédence - causalité

Def. \(a \rightarrow b\) ssi...

événements concurrents

Deux événements qui ne sont pas causalement dépendants l'un de l'autre sont dis concurrents.

#algorithmes #fr #distributedalgorithms #sorbonne

Horloge scalar

• \(T = \mathbb{N}\)
• Tous les messages portent l'horloge de leur émetteur à l'instant démission (estampillage)
• 2 règles de mise à jour:
  • R1. avant tout événement, le processus \(i\) exécute \(C_i = C_i + d, d>0\)
  • R2. lorsque le site \(i\) reçoit un message portant une estampille \(C_{msg}\) \(C_i = \max(C_i, C_{msg})\) Appliquer R1 Délivrer le message

Propriétés

• \(C\) respecte la causalité
• \(C\) capture la causalité mais ne la caractérise pas.
• \(C(e) = n\) implique que \(n-1\) événements se sont déroulés séquentiellement avant \(e\)

Les horloges scalaires peuvent être utilisées pour définir un ordre total sur les événements. On complète la date logique d'un événement par le numéro du processus où il s'est produit \(D(e) = (C_i, i)\) \(e_i \ll e_j \Leftrightarrow C(e_i) < C(e_j) \text{ ou } [C(e_i) = C(e_j) \text{ et } i < j]\)

Attention: notez que s'il y a pas d'identité, on n'a pas d'ordre total

#algorithmes #fr #distributedalgorithms #sorbonne

Horloge vectoriel

• \(T = \mathbb{N}^N\)
• chaque processus \(i\) gère un vecteur \(VC_i\) de taille \(N\).
  • \(VC_i[i]\): nombre d'événements du proc \(i\)
  • \(VC_i[j]\): connaissance qu'a \(i\) de l'avancement de l'horloge de \(j\)
• À tout instant, l'état réel d'avancement du système est donné par \(W=(VC_1[1],...,VC_N[N])\)

algorithme de mise à jour

• À chaque événement de \(P_i\), le processus exécute \(VC_i[i] = VC_i[i] + 1\)
• À l'emission d'un message \(m\): rien à faire.
• À la réception d'un message \(m\) portant un horloge \(m.VC\).
• \(\forall x: VC_i[x] = \max(VC_i[x], m.VC[x])\text{ et } VC_i[i] = VC_i[i] + 1\)

causalité

• on a les relations
  • \(VC_i \leq VC_j \Leftrightarrow \forall k: VC_i[k] \leq VC_j[k]\)
  • \(VC_i < VC_j \Leftrightarrow VC_i[k] \leq VC_j[k] \text{ et } VC_i \neq VC_j\)
  • \(VC_i | VC_j \Leftrightarrow (VC_i \leq VC_j) \wedge (VC_i \leq VC_j)\)
• Les horloges vectorielles définissent un ordre partiel sur les événements
• Les horloges vectorielles caractérisent la causalité (consistence forte) \(e\rightarrow e' \Leftrightarrow VC(e) < VC(e')\) \(e | e' \Leftrightarrow VC(e) | VC(e')\)
• augmentent la quantité d'info à gérer localement et circulant sur la réseau
• la causalité des événements d'un système réparti avec \(N\) processus ne peut être caractérisée qu'avec des horloges vectorielles ayant au moins \(N\) entrées
• détection à la volée du respect de l'ordre causale impossible et donc délivrance causale non respectée

#algorithmes #fr #distributedalgorithms #sorbonne

Horloge matricielle

• \(T = \mathbb{N}^{N^2}\)
• chaque processus gère une matrice \(MT_i\) de taille \(N^2\).
  • \(MT_i[i,i]\): nombre d'événements du processus \(i\).
  • \(MT_i[i,*]\): nombre de messages envoyés par \(i\) aux autres.
  • \(\text{diag}(MT_i)\): nombre d'événements locaux des autres sites dont \(i\) a la connaissance = horloge vectoriel du processus \(i\).
  • \(MT_i[j,k]\): nombre de messages émis par \(j\) à \(k\) dont \(i\) a connaissance.

algorithme de mise à jour

• Pour le processus \(i\):
  • à chaque événement local: \(MT_i[i,i] = MT_i[i,i] + 1\)
  • à chaque émission d'un message \(m\) vers \(j\): \(MT_i[i,i] = MT_i[i,i] + 1\) et \(MT_i[i,j] = MT_i[i,j] + 1\)
  • à chaque réception d'un message \(m\) émis par \(j\), il faut s'assurer que:
    • tous les messages envoyés antérieurement par \(j\) à \(i\) ont été reçus
    • tous les messages reçus par \(i\) et dont l'envoi de \(m\) depend causalement ont bien été reçu

considerations

• Très coûteux en espace, sur les messages et en calcul
• Le processus \(i\) sait que tous les autres processus \(p_j\) savent que le temps local de chaque \(p_k\) a progressé jusqu'au moins \(t\): \(\min(MT_i[k,l])\geq t\)
• permet d'implementer FIFO.

#algorithmes #fr #distributedalgorithms #sorbonne

Datation

à chaque événement on associé la date d’occurrence

\[ a \longmapsto D(a) \]

objectif: trouver un système de datation \(D\) qui respecte et représente au mieux la relation précédence causal.

• respecte: \(a \rightarrow b \Rightarrow D(a) < D(b)\)
• représente: \(a \rightarrow b \Leftarrow D(a) < D(b)\)

#algorithmes #fr #distributedalgorithms #sorbonne

Critères d'evaluation

La complexité en nombre d'operations est peu significative.

Si la complexité en nombre total de messages échangés est pris, donc on a un critère biaisé si les tailles de messages sont très differentes.

Complexité en temps

En l'absence d'horloge globale 2b4-temporal-models, on utilise une notion idéalisée du temps:

• les temps d'execution d'un pas de calcul est nul
• le temps de transmission d'un message nécessite une unité de temps

Alors la complexité en temps = longue de la plus longue chaîne de messages.

#algorithmes #fr #distributedalgorithms #sorbonne

Verification d'un algorithme réparti

Problème: non déterministe + multiplication des traces d'exécution + difficulté de reproduire une exécution + extrêmement difficile à debugger On utilise donc méthodes inductives basées sur des propriétés invariants et stables.

• sûreté. rien de mauvais ne se produit dans l'exécution
  • l'exclusion mutuelle: au plus un proc finit en section critique
  • détection de la termination: pas de fausse detection
• vivacité. quelque chose de bien finit par se produire dans l'exécution
  • exclusion mutuelle: si un proc demande la section critique, donc il fini par l'obtenir
  • detection del a termination: si l'application se termine, donc cette termination sera detecté.

#algorithmes #fr #distributedalgorithms #sorbonne

Algorithmes à vagues

Les algorithmes à vagues sont utilisés pour diffuser une info sur le réseau, découvrir la topologie du réseau, rassembler des informations du réseau.

Types de nœuds

• initiateur. le premier événement est interne pour démarrer l'algorithme à vague.
• non-initiateur. le premier événement est la reception du message.

Souvent, il y aura une racine ou initiateur, et les autres. Mais, il n'en reste pas moins qu'il soient plus d'un initiateur.

Propriétés

• terminaison. toute execution est finie
• décision. une décision doit être prise à terme par au moins un processus. Typiquement une retourne
• dépendance. une décision est précédée causalement par un événement de chaque processus

anneau 2b7a-wave-algorithm-ring

arbre 2b7b-wave-algorithm-tree

echo 2b7c-wave-algorithm-echo

phase 2b7d-wave-algorithm-phase

depth-first token circulation 2b7f-wave-algorithm-dftc

algorithme d'Awerbuch Circulation de jeton en profondeur d'abord 2b7e-wave-algorithm-dftc-awerbuch

#algorithmes #fr #distributedalgorithms #sorbonne

L'algorithme de l'anneau

\(p\) initiateur:

\[ \begin{align}

S_p: &\left { \text{ spontanément, une fois }\right} \\ &\text{envoi } <> \text{ au successor } \\\\

R_p: &\left { \text{ un message } <> \text{ arrive }\right} \\ &\text{réception de } <> \\ &\text{Rec}_p = true\\\

D_p: &\left { \text{Rec}_p\right} \\ &\text{décision} \end{align} $$

\(p\) non-initiateur:

$$ \begin{align}

S_p: &\left{ \text{ un message } <> \text{ arrive }\right} \\ &\text{envoi } <> \text{ au successor } \\ &\text{Rec}_p = true\\\\\

R_p: &\left { \text{ un message } <> \text{ arrive }\right} \\ &\text{réception de } <> \\ &\text{Rec}_p = true

\end{align} \]

#algorithmes #fr #distributedalgorithms #sorbonne

L'algorithme de l'arbre

algorithme symétrique

R_p : { un message <> arrive de q }
	réception de <>;
	Rec_p[q] = true;

S_p : { exists q in Vois_p : for all r in Vois_p, r != q : Rec_p[r] et !sent_p }
	envoie <> à q;
	sent_p = true;

D_p : { forall q in Vois_p : Rec_p[q] }
	décision

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

Exclusion mutuelle

Objectif. coordonner des processus se partageant une resource commune.

On va étudier le cas ou les processus sont repartis et ne communiquent que par passage de messages

Transitions d'un processus

états: requesting, not_requesting, critical_section

┌──────────┐   request()   ┌─────────┐
│ not_req  ├──────────────►│   req   │
└──────────┘               └────┬────┘
      ▲                         │     
      │                         │     
  release()                  aquire() 
      │      ┌──────────┐       │     
      └──────┤ crit_sec │◄──────┘     
             └──────────┘             

Un algorithme d'exclusion mutuelle doit garantir:

• au plus un processus exécutant la section critique
• pas d’interblocage
• pas de famine

algorithmes centralisés 2b8a-distributed-mutex-centralized

algorithmes répartis 2b8b-distributed-mutex-non-centralized

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

Exclusion mutuelle centralisée

• Le processus coordinateur est le seul à prendre une décision sur l'accès à la section critique
• Tous les infos nécessaires pour l'algorithme sont concentrés dans le coordinateur. e. g. une file d'attente (FA)

Evaluation

• On a besoin d'échanger au moins 3 messages par exécution de section critique: request, confirmation d'acquis, sors de la section critique
• equitable. les requêtes sont traitées par ordre d'arrivée
• inconvénients:
  • goulot d'étranglement sur le coordinateur
  • panne du coordinateur relativement complexe à résoudre

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

Exclusion mutuelle répartie

à base de permission

• afin d'entrer en section critique, un processus doit demander la permission à d'autre processus
• le droit d'entrée en section critique est acquis lorsque le processus a obtenu un nombre suffisant de permissions

algorithmes

Lamport 2b8b1-lamport-mutex

Ricard-Agrawala 2b8b2-ricart-agrawala-mutex

Maekawa 2b8b3-maekawa-mutex

à base de jeton

• La permission pour rentrer en section critique est réalisée par la possession d'un jeton
  • l'unicité du jeton assure la sûreté
• Le mouvement perpétuel du jeton assure la vivacité

algorithmes

On étudie des algorithmes qui dependent d'une topologie particulière

• anneau. l'algorithme de Martin 2b8b4-martin-mutex
• graphe complet. l'algorithme de Susuki-Kasami 2b8b5-susuki-kasami-mutex
• arbre.
  • l'algorithme de Raymond 2b8b6-raymond-mutex
  • l'algorithme de Naimi-Trehel 2b8b7-naimi-trehel-mutex

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

Lamport mutex (1978)

Hypothèse

• N processus
• Canaux FIFO

Si les canaux ne sont pas FIFO, l'exclusion mutuelle n'est pas garantie

Messages

• types:
  • REQUEST
  • REPLY
  • RELEASE
• contenu: (type, (H_i, S_i))

Variables locales du processus i

• H_i. horloge logique scalaire
• FA_i. file d'attente de requêtes
  • dans l'ordre induit par la valeur de leurs estampilles
• At_i. attente de permission

L'algorithme

Variables locales

FA_i = {}
H_i = 0
At_i = 0
R_i = {1, 2, ..., N} - {S_i}

Request_SC

H_i++;
Placer sa requête req_i dans la file d'attente;
Envoyer REQUEST à tous les autres sites (At_i = R_i - S_i)
Attendre l'accord de tous dles autres sites (REPLY) et que sa propre requête soit la plus ancienne de toutes (At_i = {} et req_i == head(FA_i));

Release_SC(S_j)

H_i++;
Diffuser un message RELEASE à tous les autres sites (R_i - {S_j});
Enlever sa requête req_i de la file d'attente FA_i;

Reception(msg de S_j)

Mettre à jour H_i (H_i = max(H_i, H_j) + 1);
Switch(type msg)
	REQUEST:
	    FA_i.push(msg S_j) dans l'ordre des estampilles;
	    send(REPLY, S_j);
	REPLY:
		At_i = At_i - {S_j};
	RELEASE:
		FA_i = FA_i - {msg S_j};

Evaluation

• \(3(N-1)\) messages par exécution de section critique
• sûreté. seul le site en tête de la file d'attente FA pourra rentrer en section critique. Les autres attendent que cette demande soit retirée avec un reception de RELEASE
• vivacité. toute demande finira par avoir la plus petite estampille et donc se trouvera en tête de la file d'attente
• equitable. par l'ordre total
• avantage. simplicité (en fonctionnement normal)
• inconvénients.
  • hypothèse de canaux FIFO
  • pas extensible

amélioré par Ricart-Agrawala 2b8b2-ricart-agrawala-mutex

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

Ricart-Agrawala (1981)

C'est une amelioration de l'algorithme de Lamport 2b8b1-lamport-mutex

• File d'attente. chaque processus P_i ne conserve dans sa file d'attente FA_i que les requêtes dont l'acquittement a été différé.
• RELEASE est remplacé par le message REPLY qui possède le sens 'dune autorisation d'accès, délivrée de façon conditionnelle.

Hypothèse

• N processus connu de tous
• communication fiable mais pas FIFO

Messages

• types:
  • REQUEST. demande d'entrer en section critique
  • REPLY. réponse à la reception d'un message REQUEST
  • RELEASE
• contenu: (type, (H_i, S_i))

Variables locales du processus i

• H_i. horloge logique scalaire
• FA_i. file d'attente de requêtes
  • dans l'ordre induit par la valeur de leurs estampilles
• At_i. attente de permission
• Etat_i. req, not_req, crit_sec

L'algorithme

Variables locales

FA_i = {}
H_i = 0
At_i = 0
R_i = {1, 2, ..., N} - {S_i}

Request_SC

H_i++;
Envoyer REQUEST à tous les autres sites (At_i = R_i - S_i)
Attendre l'accord de tous dles autres sites (REPLY);

Release_SC(S_j)

H_i++;
Diffuser un message REPLY à tous les autres sites differés dans la FA_i;

Reception(msg de S_j)

Mettre à jour H_i (H_i = max(H_i, H_j) + 1);
<...>

Evaluation

• \(2(N-1)\) messages par exécution de section critique
• sûreté. seul le site en tête de la file d'attente FA pourra rentrer en section critique. Les autres attendent que cette demande soit retirée avec un reception de RELEASE
• vivacité. toute demande finira par avoir la plus petite estampille et donc se trouvera en tête de la file d'attente
• equitable. par l'ordre total
• avantages.
  • hypothèse de canaux FIFO plus nécessaire
  • taille de la file d'attente FA plus petite
  • moins de messages envoyés par rapport Lamport
• inconvénients.
  • pas extensible

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

Maekawa (1985)

• Chaque site ne peut donner sa permission qu'a un seul site à la fois
• Chaque site S_i appartient à un ensemble (quorum) RS_i (Request Set) dont il doit obtenir l'accord (msg LOCKED) de tous les membres pour pouvoir entrer en section critique
• Il doit y a voir au moins un site commun entre deux ensembles RS_i et RS_j. Ce site arbitre les conflits. C'est-à-dire: \(\forall i,j ¸in \left{1,...,N\right} \text{ tq } i\neq j, \text{RS}_i \cap \text{RS}_j \neq \emptyset\)

Afin de minimiser le trafic des messages et de demander le même effort à tous les sites:

• Soit
  • N : nombre de sites
  • K_i = |RS_i|
  • D : nombre d'ensembles auquel chaque site appartient
• K_i= K, pour tout i dans { 1, ..., N}
• S_i est dans RS_i, pour tout S_i dans { S_1, ...,S_n }
• Pour tous i != j dans { 1,..., N}, S_i et S_j appartiennent à D ensembles RS
• D = K est une possibilité

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

L'algorithme de Martin

Le jeton circule dans le sens inverse des requêtes Quand S_i veut entrer en section critique, il envoie une requête à son successeur et attend le jeton. En recevant une requête de son prédécesseur, si S_j ne possède pas le jeton, il retransmet la requête à son successeur. Sinon, s'il le possède et ne l'utilise pas, il l'envoie à son prédécesseur.

Evaluation

• Nombre de messages: \(2(K+1)\), dont K est le nombre de sites entre le demandeur et le site en possession du jeton
• avantages
  • simplicité
  • pas de diffusion
• inconvénients
  • pas extensible
  • un site qui n'est pas intéressé par la section critique est souvent solicité à transmettre les requêtes et le jeton

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

L'algorithme de Susuki-Kasami

À chaque envoi du jeton, le processus expéditeur envoie aussi la file d'attente et un tableau qu'a l'information de la dernière demande d'entrée en section critique.

Types de message

• REQUEST (S_j, k). indique que site S_j est en train de faire sa k-ème demande d'entrée en section critique
• TOKEN (Q, LN)
  • Q. une file d'attente de demandes pour entrer en section critique
  • LN. LN[i] indique le numéro de la dernière demande d'entrée en section critique du site S_i qui a été satisfaite

l'algorithme

variables

• etat_i. req, not_req, crit_seq
• token_i
• RN_i
  • RN_i[j] est le numéro de la dernière requête reçue de la part du site S_j
  • RN_i[i] correspond au nombre de requêtes faites par le site S_i
• LN_i. vecteur de N positions de requêtes satisfaites

initialisation (S_i)

token = S_i == S_1
etat = not_req
RN = [ 0 for j in 1...N ]
LN = [ 0 for j in 1...N ]
Q = {}

Request_CS(i)

etat = req

if token == false
	RN[i]++
	diffuser (REQUEST (S_i, RN[i]))
	/* attendre token == true */

etat = crit_sec

Release_CS(i)

LN[i] = RN[i]

for site in [ 1,...,N ]
	if site != i et not site dans Q and RN[site] > LN[site]
		Q.push_back(site)

if Q not empty
	token = false
	site = Q.pop()
	send(TOKEN(Q, LN)) à site

etat = not_req

Receive_request_CS(S_j, REQUEST(j, k))

RN[j] = max(RN[j], k)

if token == true and etat == not_req and RN[j] > LN[j]
	token = false
	send(TOKEN(Q, LN)) à S_j

Receive_token(TOKEN(Q, LN))

token = true
LN = TOKEN.LN
Q = TOKEN.Q

Evaluation

• Nombre de messages par exécution de section critique
  • N, si le processus n'a pas le jeton
  • 0, si le processus a le jeton
• vivacité. garantie par l'ordre FIFO de la file Q
• inconvenient. pas extensible

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

L'algorithme de Raymond

Les processus sont organisés en arbre ayant pour racine le site qui possède le jeton. Les arêtes sont orientés vers la racine

Les demandes du jeton sont propagées vers la racine et sont enregistrées dans une file local sur chaque site du trajet

Chaque nœud possède

• une variable holder qui pointe en direction du nœud racine.
• file FIFO pour sauvegarde les requêtes pendantes de ses voisins L'arbre est modifié (inversion du pointeur) à chaque transmission su jeton

l'algorithme

• Lorsqu'un nœud demande le jeton ou reçoit une requête pour le jeton de ses voisins, le nœud ajoute la requête dans sa file locale. Si la file était vide, il renvoie un requête à son holder.
• En recevant une requête, le nœud qui possède le jeton le libère lorsqu'il ne l'utilise plus. À chaque libération du jeton, un nœud inverse la direction de holder.
• Lorsqu'un nœud reçoit le jeton, il enlève le premier élément (first) de sa file.
  • Si first est le propre nœud, il rentre en section critique
  • Sinon, le jeton est renvoyé à first
• Si la file n'est pas vide, une requête pour le jeton est renvoyé au voisin

si on ignore les directions des arcs, la topologie de l'arbre n'est pas modifié.

Evaluation

• Entre 0 et N messages par demande de section critique
• moyenne de O(log(N)) messages par exécution de section critique
• avantages.
  • extensibilité

#algorithmes #fr #distributedalgorithms #sorbonne #mutex

L'algorithme de Naimi-Trehel

On a deux estructures de données:

• File de requêtes (next)
  • Le processus en tête de la file possède le jeton
  • Le processus à la fin de la file est le dernier processus qui a fait une requête pour entrer en section critique
  • Une nouvelle requête est toujours placée en fin de la file
• Arbre de chemins vers le dernier demandeur (father)
  • Le dernier demandeur est la racine de l'arbre
  • Une nouvelle requête est transmise à travers un chemin de pointeurs father jusqu'à la racine de l'arbre (father == nil)
    • Reconfiguration dynamique de l'arbre. Le nouveau demandeur devient la nouvelle racine de l'arbre
    • Les sites dans le chemin compris entre la nouvelle et l'ancienne racine changent leur pointeur father vers la nouvelle racine

L'algorithme

variables locales

token
requesting
next
father

initialisation de S_i

father = S_1;
next = nil;
requesting = false;
token = (father == S_i);

if father == S_i
	father = nil;

Request_CS(S_i)

requesting = true;

if father != nil
	send(REQUEST, S_i) à father;
	father = nil;

/* attendre token == true */

Release_CS(S_i)

requesting = true;

if next != nil 
	send(token) à next;
	token = false;
	next = nil;

Receive_request_CS(S_j)

if father == nil;
	if requesting
		next = S_j;
	else
		token = false;
		send(token) à S_j;
else
	send(REQUEST, S_j) à father;

father = S_j

Receive_token(S_j)

token = true

Evaluation

• Entre 0 et N messages par demande de section critique
• moyenne de O(log(N)) messages par exécution de section critique
• avantages.
  • extensibilité
  • adaptativité. un site qui n'est pas intéressé par la section critique ne sera plus sollicité après quelques transferts de requêtes.

#fr #distributedalgorithms #sorbonne

Detection de la termination

Definition

Construction d'une couche de contrôle afin de détecter la terminaison d'une application répartie.

Le but c'est de distinguer l'algorithme de détection de terminaison de l'algorithm de l'application. Il a pas d'influence dans l'exécution de l'application

• Configuration terminale
  • aucune action supplémentaire de l'appli ne peut être exécutée
  • tous les canaux de communication sont vides
• Etat
  • actif. si une action interne ou l'action emmètre est applicable
  • inactif. dans le cas contraire
• Message
  • applicatif.
  • contrôle. message de l'algorithme de detection de la terminaison

Un modèle est défini pour un exécution répartie en définissant les actions des processus actifs et inactifs

Les processus suivent les règles suivantes

1. initialement chaque processus \(p\) peut être dans l’état actif ou inactif
2. un processus \(p\) peut passer spontanément de l’état actif a inactif
3. seul les processus actifs peuvent envoyer des messages application
4. lors de la réception d'un message application, un proc \(p\) inactif passe a actif
   • seule façon pour un processus inactif de passer actif observations

• un message de contrôle émis lorsque le processus est inactif ne le rend pas actif.
• la reception d'un message de contrôle non plus.

Terminaison

• \(P\): ensemble de processus
• \(C\): ensemble de canaux
• Prédicat TERM
  • TERM <-> (\(\forall p \in P: p \text{ inactif}) \text{ et } (\forall c \in c : C \text{ vide})\)
    • TERM est un prédicat stable:
      • \(\text{TERM}(t) = \text{true} \Rightarrow \forall t' > t: \text{TERM}(t') = \text{true}\)

Propriétés

• sûreté. si un proc detecte la terminaison a l'instant \(t\), alors\(\text{TERM}(t) = \text{true}\)
  • pas de fausse detection.
• vivacité. si a un instant \(t, \text{TERM}(t) = \text{true}\), alors l'algorithme de detection finira par détecter cette terminaison.

Example d'un mauvais algo:

• les sites se trouve soit dans l'état inactif soit dans l'état actif
• algo
  • faire circuler un jeton (message contrôle) selon une structure d'anneau, envoyé initialement par \(P_0\)
  • Lorsqu'un site est inactif et possède le jeton, il l'envoie au site suivant.
  • lorsque le jeton revient à \(P_0\), la terminaison est détectée

Algorithmes

• algorithme de Misra (1983) 2b91-algorithme-misra

Modèle à communication instantanée

• A communication instantanée
  • communication synchrone: exemple CSP
  • TERMP <-> forall p in P : p inactif
• Atomique
  • le moment d'actividte de procesus est négligeable
    • TERM <-> forall c in C: c vide

Algorithme de Rana (1983)

• Communication instantanée (e.g. CSP)
• N sites organisés dans un anneau logique unidirectionnel
  • messages transmis sur l'anneau
• A chaque fois qu'un processus recoit soit un message applicatif soit un message de controle, il met son horloge logique local a jour
• Les messages de controles circulent sur l'anneau
• ...
• ...

l'algo

• lorsqu'un proc devien inactif, il enregistre la valeur de son horloge local (H_ina) et envoie le message de control <H_ina, 1> a son succ
• lors de la réception d'un message de controle:
  • si le site est actif, il ignore le message
  • sinon
    • si compteur != N
      • si la valeur de son passage a inactif H_ina > H_msg du message de control recu, le message est ignoré
      • Sinon, le message est envoye...

Algorithme de Dijkstra (1983)

• modele a communication instantanée
• N sites organisés dans un anneau logique
• Existence d'un jeton
• Les sites peuvent etre de couleur blanc ou noire ainsi que le jeton
  • initialement tous les sites et le jeton son blancs

l'algo

• il y a un site initiateur P_0
  • quand P_0 devient inactif, il envoie le jeton couleur blanche a P_N-1
• lorsque le site P_i, qui detient le jeton, devient inactif, P_i envoie le jeton au site P_i-2
  • Si P_i est blanc
    • P_i envoie a P_i-1 le jeton sans changer la couleur du jeotn
  • sinon
    • P_i change la couleur du jeton a noire avant de l'envoyer a P_i-1
    • P_i devient blanc
• Un site P_i devient noire en envoyant un message applicatif au site P_j
• Lorsque P_o recoit le jeton
  • si le jeton est blanc et P_o est blanc et dans l'etat inactif
    • terminaison détectée
    • sinon
      • lorsque P_0 devient inactif, il renvoie le jeton couleur blanche a P_N-1

l'algo en utilisant un arbre couvrant

• Racine informe aux feuilles de commencer la détection
  • chaque feuille a un jeton blanc
  • un site P_i devient noire en envoyant un message applicatif au site P_j
  • Si P_i est noir:
    • P_i change la couleur du jeton a noire avant de l'envoyaer a son pere
    • P_i devient blanc
  • Si P_i a recu un jeton noir d'un de ses enfants, il envoie un jeton tnoir a son pere
  • ...

Modèle atomique

L'algorithme de détection ne voit jamais un processus local dans l'état actif: l'algorithme n'est activé que lorsque le procsssus est inactif

Ex: mauvaise solution avec deux compteurs

• N procs
• supposons qu'un processus i veut savoir si le systeme se trouve dans un etat terminal: tous les canaux vides
  • i envoie un message de controle a tous les N-1 autres procs a un instant t
• Chaque processus j répond a i avec le nombre de messages recus r_j(t) et nombre de messages envoyés s_j(t)
• en recevant tous les messages, le site i calcule +
  • ...

L'algorithme de quatre compteurs

• Mattern (1987)
• Compteur deux fois
  • fin de la premiere vague de controle. l'initiateur accumule les valeurs de s_i(t_i) et r_i(t_i) forall i: 1 <= i <= N dans S et R
  • fin de la deuxieme vague de controle. l'initiateur accumule les valeurs de s_i(t_i) et r_i(t_i) forall i: 1<=i<=N dans S' et R'
• Si R=S', alors, l'exécution s'est terminée à la fin de la premiere vague (à prouver) il faut bien reviser les preuves

#fr #distributedalgorithms #sorbonne

algorithme de Misra (1983)

• Anneau logique
  • canaux FIFO unidirectionnels
• chaque site une couleur noir ou blanc
  • noir -> actif
  • blanc -> inactif
• jeton porte un compteur
• N sites
• Terminaison: tous les sites sont blanc après un tour

init:
	state = actif
	color = black
	if i == 0 :
		token = true
	else
		token = false

Upon fin:
	state = inactif

Upon reception applictation message:
	etat = actif
	color = black

Upon reception TOKEN(count):
	token = true
	nb = count
	if nb == N and color == white
		termination detection

#infosec #security #information #sorbonne #fr

Sécurité des systèmes d'information

La sécurité des systèmes d'information est un ensemble des techniques, outils pratiques et politiques visant garantir la sûreté (3a-surete) et la sécurité(3b-securite) des systèmes d'information. Il est fortement liée aux données, sa disponibilité, intégrité et confidentialité

#sorbonne #infosec #fr

Sûreté

C'est le degré de confiance que peut accorder les utilisateurs dans le service délivré. Elle est liée à la disponibilité (3a1-disponibilité) et la fiabilité (3a2-fiabilité).

#sorbonne #infosec #fr

Disponibilité 1

C'est la capacité à être prêt à délivrer le service (dans les meilleures conditions) ²

#infosec #sorbonne #fr

Fiabilité 1

C'est la propriété ou caractère d'un système d'assurer la continuité de ses services (pas d’arrêt) ²

#sorbonne #infosec #fr

Sécurité

La sécurité de fonctionnement d'un système d'information se décompose en deux aspects:

• safety 3b1-safety
• security 3b2-security

Selon le cours SAS, il faut retenir les 5 piliers de la sécurité:

• confidentialité 3b4-confidentialite
• authentification 3b3-authentification
• intégrité 3b5-integrite
• non répudiation 3b6-non-repudiation
• auditabilité 3b7-auditabilite on considere aussi la vie privée et l'anonymat 3b8-vie-privee, 3b9-anonymat

Les politiques de sécurité 3b10-security-policies

#sorbonne #fr #infosec

Safety

évitement des situations catastrophiques.

#infosec #sorbonne #securitypolicy

Les politiques de sécurité

Étapes pour une politique de sécurité

1. Definition de la politique
2. Identification des vulnérabilités.
3. Évaluation des probabilités associées à chacune des menaces
4. Évaluation du coût d'une intrusion réussie
5. Choix des contre mesures
6. Évaluation des coûts et de l'adéquation des contres mesures
7. Décision. Application et mis en place de solution.

La réalisation d'une politique de sécurité résulte de la mise en oeuvre cohérente de

• moyens physiques
• moyens informatiques
• règles d'organisation et moyens procéduraux Ces moyens doivent être
• complets
• non contradictoires et raisonnablement contraignants
• homogènes par rapport aux risques et aux attaques considérés
• respectés La base de la réalisation de la sécurité sont
• le confinement
• le principe du moindre privilège

Mèthodes

• MEHARI. Methode Harmonisée d'Analyse de RIsques
• EBIOS. Expression des Besoins et Identification des Objectifs de Sécurité
• ISO/CEI 27XXX

#sorbonne #infosec #fr

Security

préservation de la confidentialité et de l’intégrité des informations.

#sorbonne #fr #infosec

authentification

C'est la propriété qui assure la reconnaissance sûre de l’identité d’une entité. Il protège contre l'usurpation d'identité 3b3f-deguissement-mascarade On propose un défi à l'entité que veut authentifier dans un système: un mot de passe, une identification, un jeton, un graphisme, etc.

Il y a tellement des méthodes d'authentification...

kerberos 3b3a-kerberos

#infosec #cybersec #auth #fr

Kerberos protocol

Développé au MIT pour le projet Athena, c'est un protocole d'authentification mais pas de autorisation. C'est-à-dire, même si la plateforme procure l'information des droits, c'est à les applications de les vérifier. Il fonctionne en utilisant des tickets (3b3d-kerberos-tickets). Les tickets sont demandés au KDC (3b3b1-kerberos-kdc) et sont utilisé pour s'authentifier dans les différents services de la réseau. Le protocol utilise du cryptage symétrique.

Ports utilisés

Au niveau de transport, Kerberos utilise par default:

workflow 3b3e-kerberos-workflow agentes ou entités dans Kerberos 3b3b-kerberos-agents clés de chiffrement 3b3c-kerberos-keys tickets de kerberos 3b3d-kerberos-tickets attaques au Kerberos 3b3a1-kerberos-attacks

#kerberos #cybersec #attack #fr #activedirectory

Attaques au protocole Kerberos

Il y a plein d'attaques au protocole Kerberos.

• kerberoasting 3b3a2-kerberoasting
• pass-the-hash attack 3b3a3-pass-the-hash-attack
• golden ticket attack 3b3a4-golden-ticket-attack
• silver ticket attack 3b3a5-silver-ticket-attack

Quelques outils

• enum AD without RSAT
• Other-Tools-AD

#kerberos #cybersec #auth #fr #infosec #activedirectory

Agentes dans Kerberos

Grosso modo, on a

• client ou usager.
• le Serveur Application (AP)
• Centre de distribution des clés (KDC) 3b3b1-kerberos-kdc

l#kerberos #fr #infosec #cybersec #activedirectory

KDC

Si on parle d'Active Directory, c'est installé dans le Domain Controller. Il est composé de trois éléments :

• Le serveur d'authentication (AS)
• Le serveur d'attribution des clés (TGS)
• la base de données La compte de service du KDC est krbtgt 3b3b2-kerberos-krbtgt

#activedirectory #kerberos #cybersec #fr #todo

krbtgt

#kerberos #activedirectory #crypto #fr

Clés dans Kerberos

C'est important d'identifier le role qui jouent des usagers dans kerberos.

• clé de KDC (krbtgt)
• clé d'usager
• clé de service
• clé de session
• clé de session du service

#kerberos #activedirectory #infosec #cybersec #fr

Tickets dans le protocole Kerberos

Il y a deux types de tickets:

• ticket de service (ST) 3b3d2-kerberos-service-ticket
• ticket principal (TGT) 3b3d1-kerberos-ticket-tgt

#kerberos #crypto #activedirectory #infosec #fr #cybersec

Ticket Granting Ticket

#kerberos #activedirectory #cybersec #fr

Le workflow de Kerberos

Tout d'abord, le client n'a aucun ticket. Du coup, il demande un TGT (3b3d1-kerberos-ticket-tgt) en envoyant un Kerberos Authentication Service Request qui contient le nom d'usager, le nom du service (maintenant kerberos), et un timestamp chiffré avec le hash NTLM (2a1a-ntlm-hash-function) de l'usager.

user ----------------->  KDC (DC)
	  [1] KRB_AS_REQ
	 <-----------------
	  [2] KRB_AS_REP   
	 -----------------> 
	  [3] KRB_TGT_REQ
	 <-----------------
	  [4] KRB_TGT_REP   

#sorbonne #infosec #fr

déguisement (mascarade)

Pour rentrer dans un système, on essaye de piéger des usagers et de se faire passer pour quelqu'un d'autre (usurpation d’identité)

Exemples

• simulation d'interface système sur écran
• simulation de terminal à carte bancaire

#sorbonne #fr #infosec

confidentialité

C'est la propriété qui assure qu'une information ne peut être lue que par des entités habilitées (selon des contraintes précises)

méthodes et outils pour sauvegarder la confidentialité

• cryptographie. 3b4a-cryptographie

attaques à la confidentialité

• man in the middle.
• analyse de trafic
• inférence.

attaques par violation de protocole

• envoie de données non prévues (trames mal-formées, séquence non prévues)

attaque par saturation

• envoie des messages trop nombreux provoquant un écroulement des systèmes et réseaux. DDoS.

attaques sociales

• arnaques
• extorsion

#crypto #infosec #fr #sorbonne

Cryptographie

Crypto-système symétrique 3b4a1-symmetric-key-algorithms

Crypto-système asymétrique 3b4a2-asymmetric-key-algorithm

L'efficacité général du cryptage dépend

• de la confidentialité des secrets
• de la difficulté à deviner les secrets ou à essayer toutes les possibilités
• de la difficulté de l'inversion de l'algorithme sans connaître la clé
• de l'existence de portes par derrière
• possibilité de déchiffrement par attaque à text partiellement connu

Fonctions à sens unique

#todo C'est une fonction \(f(M)\) facile à calculer mais telle qu'il est extrêmement difficile de déduire \(M\) de \(f(M)\).

• \(h\) est à collision faible difficile: il est calculatoirement difficile de trouver M significatif tel que \(h(M) = K\) pour un signature \(K\).
• \(h\) est à collision forte difficile: il est calculatoirement difficile de trouver deux \(M\) et \(M'\) tel que \(h(M) = h(M')\) Une fonction de hachage est avec clef si son calcul dépend aussi d'une info secrète. C'est-à-dire, \(k \neq k' \Rightarrow H_k(M)\neq H_k(M)\) . Voir HMAC (code d'authentification de message de hachage à clé).

fonction d'hachage cryptographic 2a1-cryptographic-hash-function

Glossaire

• Décrypter ou casser un code
• L'art de définir des codes (de chiffrement) est la cryptographie
• L'art de casser des codes est appelé cryptanalyse ou cryptologie
• Le chiffrement est donc une transformation d'un texte pour en cacher le sens
• Le déchiffrement est l'opération inverse permettant de récupérer le text en clair à partir du texte chiffré
• Un crypto-système est l'ensemble des deux méthodes de chiffrement et de déchiffrement utilisable en sécurité

#crypto #infosec #fr #sorbonne

Crypto-système symétrique

On prefers les crypto-système symétriques à cause de son effectivité pratique pour chiffrer l'info

exemples

• substitution como alphabétique
• substitutions de polygrammes
• par transposition
• ECB
• CBC
• DES 3b4a1a-DES

#crypto #infosec #fr #sorbonne

Crypto-système symétrique

On a une clef publique et une clef privée: deux morceaux du secret.

Exemples

• RSA 3b4a2a-RSA

#todo

RSA

histoire

algorithme

#sorbonne #infosec #fr

intégrité

C'est la propriété qui assure qu'une information n'est modifiée que par des entités habilitées (selon des contraintes précises)

L’intégrité peut être vérifiée avec une signature ou avec l'empreinte numérique d'une fonction d'hachage cryptographique (2a1-cryptographic-hash-function).

fonction signature 3b5b-digital-signature

attaques sur l'intégrité 3b5a-attacks-integrity

#sorbonne #infosec #attack #integrity

Attaques sur l'intégrité

intégrité des données

• Modification des données.

intégrité des protocoles

• répétition de l'opération pour obtenir une fraude.

intégrité des programmes

• modifications à caractère frauduleux ou de sabotage
• infections à caractère unique: introduction d'un comportement illicite avec un trigger
• infections auto-reproductrices: virus, ver, rootkit, etc

#todo #sorbonne #infosec #fr

3b5b-digital-signature

content

#infosec #sorbonne #fr

non repudiation

C'est la propriété qui assure que l'auteur d'un acte ne peut ensuite dénier l'avoir effectué. D'un coté, un message ou une transaction ne peut être nié.e par son émetteur. D'autre coté, un récepteur ne peut ultérieurement nier avoir reçu un ordre.

Par contre, on souvent cherche la repudiation pour protéger l'identité d'un témoin ou un source journalistique.

#sorbonne #infosec #soc #fr

auditabilité

C'est la propriété qui assure la capacité à détecter et à enregistrer de façon infalsifiable les tentatives de violation de la politique de sécurité.

#infosec #fr #sorbonne

Anonymat

L’anonymat est l’état (dans un « système informatique ») d’être inconnu et non identifiable.

L'anonymat est quelque chose difficile à obtenir aujourd'hui. Pourtant, on peut minimiser l'impact qu'on a sur internet en utilisant des méthodes. r/Piracy

#cybersec #fr

Cyber sécurité

C'est la pratique à proteger les systèmes, les réseaux, les programmes des attaques (4a-cyber-attaques).

#cybersec #hacking #fr

cyber attaques

Les cyber attaques e

Les points d'entrée d'un cyber attaques sont des vulnérabilités 4a1-vulnerabilites.

Classement

On peut classer les cyber attaques de nombreuses formes.

3b3a1-kerberos-attacks

4a2-side-channel-attacks

#cybersec #fr #vulnerabilites

vulnérabilités

impact

L'impact d'un cyber attaque potentiel à cause d'une vulnérabilité donné peut être quantifier en voyant comment il affecte la 3a1-disponibilité, la 3b4-confidentialite et la 3b5-integrite de l'information. Il est quantifié en utilisant le CVSS.

#cybersec #hacking #fr #sidechannel #attack

attaques par canal auxiliare

C'est une attaque dont le but est obtenir information à partir de l'implementation inhérente d'un protocole, algorithm ou architecture.

SysBumps 4a3-sysbumps

#cybersec #hacking #fr #sidechannel #attack #macos #arm

SysBumps

#computers #computerscience #fr

Ordinateurs

On utilise ordinateur pour faire référence à un dispositif de traitement d'information programmable. Il fonction par lecture séquentielle d'un ensemble d'instructions afin de faire des operations arithmétiques et logiques. Les ensembles d'instructions s'organisent en programmes.

Attention: a l'anglais et a l'espagnol, on souvent fait pas la difference entres les ordinateurs et les calculateurs (computers, computadoras). De ce que je vois, on utilise le terme 'ordinateur' pour ces qu'en anglais on appelle digital computers.

ordinateurs mécaniques 5a-mechanic-computers

5d-integrated-circuits

ordinateurs électroniques 5b-digital-computers

infrastructures virtuelles et conteneurs 5c-virtual-infrastructures

#computers #computerscience #fr

Ordinateur electronique

Parties d'un ordinateur

5b1-procesor

5b2-peripherics

5b4-networks

5b3-smartphones

#computers #computerscience #fr

Processeur

5b1a-risc-architecture 5b3-cisc-architecture

mpis32 5b1a1-mips32

arm 5b1a2-arm

5b1a2a-raspberry-pi

1g-android

5b1a2a1-raspberry-pi-programming

GPIOs

Les GPIOs sont associés a l'espace mémoire. Par example, dans la raspberry pi 1B, la direction base commence à 0x20200000 5b1a2a1b-rpi-register-organisation

I2C 5b1a2a1a-pi-i2c

#i2c #peripherics #arm #raspberrypi #drivers #gpio #programming

Raspberry pi I2C

Pour information especifique par rapport le bus I2C 5d2-ci-i2c

On a besoin d’installer le package i2c-toolfs pour utiliser l’i2c de la carte Raspberry pi :

sudo apt install -y i2c-tools 

sudo raspi-config

i2cdetect

https://arduinofactory.fr/raspberry-pi-i2c/

Cada GPFSELn es un registro de 32 bits, donde cada pin usa 3 bits para su configuración:

1n-drivers

#tag #tagg

content

#smartphone #en

Smartphones

1g-android

#network #en #sorbonne #fr

Computer networks

5b4b-osi-model

5b4d-tcp-ip-model

5b4a-communication-protocols

types de réseau

• Topologie
  • peer to peer 2b10-peer-to-peer
  • star
  • cluster tree
  • mesh

Solutions grand public

• ZigBee -> réseau d'objets

  • 64k noeuds : star, cluster, mesh
  • autonomie plusieurs années
  • 250 kbs
  • portée 100m

• Bluetooth -> remplacement de câbles

  • • 7 noeuds actifs
  • 0.7 à 2 Mbs
  • portée 10m

• Wi-Fi -> internet

  • 32 nœuds : star + roaming
  • autonomie en heures
  • 11 - x100 Mbs

• Bluetooth Low Energy 5b4a-ble -> IOT

  • autonomie en années
  • P2P ou Star nb de nœuds illimité
  • 300 kbs
  • 10 - 100m

• LoRaWAN -> IOT grandes distances

  • 5 - 15 km
  • autonomie en années
  • star nb de noeuds illimité
  • 50 kbs

#network #ble #bluetooth

Bluetooth Low Energy

BLE est une norme différente du bluetooth classique. Les usages sont très différents, mais les clients BT sont souvent compatibles avec les deux normes.

Objectif: fonctionner très longtemps sur une pile bouton plusieurs mois ou plusieurs années.

• BLE fonctionne sur la bande ISM de 2.4GHz sur 40 bandes espacés chacune de 2MHz.
• Utilise FHSS
• 10kBs de vitesse de transmission
• Portée a 3m - 50m théorique mais 3 - 5m en pratique
• Paquets courts (~20B) => moins de mémoire

The Host protocol layers and the Controller protocol layer are connected by a Host-Controller Interface (HCI).

Roles:

• Broadcaster
• Observer
• Peripheral
• Central

Host protocol layers

Controller protocol layers

Couche Liaison (LL)

Manage the state of the LE Radio.

Les paquets sont identifiés par leur numéro de transaction (Access Address) et pas par le couple d'identifiants (émetteur-destinataire). Cet solution permet d'économiser des octets.

Ce numéro est créé aléatoirement au moment de la connexion entre un master et un slave.

#tag #tagg

5b4a-communication-protocols

5b4a1-tcp-protocol

5b4a2-udp-protocol

5b4a3-mqtt-protocol

content

#iot #sorbonne #network

Message Queuing Telemetry Transport

• Modèle publish (topic-value) / subscribe (topic)
• décentralisée et asynchrone
• basé sur TCP 5b4a1-tcp-protocol
• développé par IBM en 1999
• adapté aux réseaux sans fils
• faible consommation énergétique Les clients doivent s'abonner et après ils reçoivent que l'information venant des autres clients.

publish                      subscribe
┌──────┐                              
│client├──────────┐                   
└──────┘          │           ┌──────┐
                  │   ┌──────►│client│
                  ▼   │       └──────┘
┌──────┐        ┌─────┴┐              
│client├───────►│broker│              
└──────┘        └─────┬┘              
                  ▲   │       ┌──────┐
                  │   └──────►│client│
┌──────┐          │           └──────┘
│client├──────────┘                   
└──────┘                                                

glossaire

• broker. distribue les informations aux clients intéressés
• client. connecté au broker pour envoyer ou recevoir ldes informations
• topic. nom du message. les clients publient ou souscrivent au topic
  • Les topics peuvent être hiérarchique: /topic/subtopic
• publish. envoi d'informations par un client au broker qui les redistribue aux clients abonnés au topic
• subscribe. abonnement à un topic pour recevoir les messages publiés. désabonnement possible.
• QoS. Quality of Service.
  • 0. au plus une seule fois sans qu'un accusé de réception
  • 1. au moins une fois, message envoyé plusieurs fois jusqu'à la réception de l'accusé de réception.
  • 2. spécifie exactement une fois, Clients expéditeurs et destinataires ont la garantie d'une seule copie du message.

#computers #computerscience #fr #sorbonne

Infrastructures Virtuelles et Conteneurs

On les appel aussi IVC. On cherche l'utilisation des composantes logiciels et la virtualisation des certains services. Les IVC tentent de fusionner les deux approches.

• l'isolation
• la gestion des services systèmes et des services applicatifs

On cherche aussi

• virtualisation des applications
• virtualisation des serveurs
• virtualisation des réseaux
• virtualisation du stockage

glossaire 5c8-virtual-infrastructures-glossary

histoire 5c9-virtual-infrastructures-history

advantages

• Le matériel virtuel émulé reste plus homogène que les matèriels physiques.
• Usage plus optimal des ressources parce qu'on peut tailler et contrôler les ressources.
• Sécurité: isolation, mise en suspend, surveillance, audit log, forensic analysis plus facile a faire.

désavantages

• limitation de la puissance
• complexification des interactions

Modèles génériques de virtualisation

• SaaS 5c5-saas
• PaaS 5c6-paas
• IaaS 5c7-iaas

Types de virtualisation

• Conteneur 5c2-container
• Virtualisation pure 5c3-virtualisation-pure
• Hybride 5c4-virtualisation-hybride

#computers #computerscience #fr #sorbonne #container

Conteneurs

isolateur ou virtualisation d'OS

• pas de système virtualisé. on utilise le même noyau que celui du système hôte.
• il y a un couche isolation/virtualisation
• isole l'exécution des application dans des contextes d'exécution
• très performante et très économique en mémoire
• on isole les systèmes des fichiers aussi

Précurseurs

Toutes les fonctionnalités des conteneurs reposent sur des services noyaux.

• ulimit
• chroot
• pivot_root
• mount
• namespace
• cgroups #todo

#computers #computerscience #fr #sorbonne #container

Virtualisation pure

Création d'une machine complète virtuelle et emulation de tous les éléments d'une machine Nécessite ce qu'on appelle un hyperviseur pour gérer des machines virtuelles et leur cohabitation.

Pour chaque application du système virtualisé, on fait deux translation d'adresse EPT (Extended Page Table) permet d'éviter ces conversions en garantissant la sécurité (isolation)

Defautes

• point de défaillance unique
• un recours à des machines plus puissantes
• dégradation des performances
• complexité accrue de l'analyse d'erreurs
• parfois inadapté et avec surcoût

types

• Hyperviseur avec architecture hébergée emulation de matériel il peut être multi-kernel exemples: VirtualBox, QEMU, Vmware (workstation, fusion,player), Microsoft Virtual PC, Parallels desktop,…
• Hyperviseur complet OS virtualisé MiniOS gestionaire comme hyperviseur. Peut émuler du matériel ou faire de la délegation exemples: XEN, KVM, Vmware vSphere
• Paravirtualisation L'hyperviseur n'émule pas du materiel: il delegue au vrai matériel (CPU/GPU) utilisable avec les instructions spécifiques des CPU souvent impracticable pour les systèmes non libres exemples: Vmware Vsphere, XEN, MicrosoP Hyper-V server, KVM

#todo

#computers #computerscience #fr #sorbonne

Hybride

• Noyau dans l'espace utilisateur un noyau linux s'exécute comme une application dans le user-space du noyau linux multi-kernel(linux seulement) pas de couche d'isolation exemple: UML (User Mode Linux) abandonnée

#todo

#computers #computerscience #fr #sorbonne #cloud

Software as a Service (SaaS)

• Accès à un logiciel au travers d'une connexion à un serveur distant
• L'accès peut être libre ou sur abonnement
• exemples: mail service, editeur en ligne, github, etc

#computers #computerscience #fr #sorbonne #cloud

Platform as a Service (PaaS)

• Le client déploie son application sur l'infrastructure cloud
• Le fournisseur fournit les briques logicielles de base: os, taille de matériel, etc
• Le fournisseur maintient la plateforme d'execution: stockage, réseau, etc
• Le fournisseur peut fournir des services en plus

#computers #computerscience #fr #sorbonne #cloud

Infrastructure as a Service (IaaS)

• Le fournisseur donne accès à des resources informatiques
• Accès souvent sous forme de machines virtuelles
• Le client installe sa propre pile logicielle sur les ressources obtenues
• Possibilité de déployer son propre OS.

#computers #computerscience #fr #sorbonne

Glossaire

• le système hôte. Os principal de l'ordinateur
• le système invité. OS installé à l'interieur d'une machine viruelle.
• machine virtuelle (VM). 5c1-virtual-machines
• virtuel device (VD). système embarqué émulé
• ordinateur virtuel
• hyperviseur. noyau ultra léger permettant la gestion le monitoring et le diagnostique des VM/VD

#computers #computerscience #fr #sorbonne

Histoire

• 1979 - 1982. UNIX chroot pour UNIX v7 et BSD
• 1990's. Émulateurs d'Atari, Amiga, NES, SNES
• 1998-2000. BSD Jail
• 2000's:
  • VMWare, VirtualBox
  • Xen, Qemu
  • Intel VTx
  • KVM
  • Linux LXC
  • Microsoft Hyper-V
  • Docker

#electronics #integratedcircuits

Circuit integré

communications

5d1-ci-gpio

5d2-ci-i2c

#integratedcircuits #protocol #serialport #pin

I2C

L'Inter-Integrated Circuit (I2C) est un protocole de communication série utilisé pour connecter des composants électroniques sur un même circuit imprimé ou entre différents périphériques.

• SDA: Serial Data Line
• SCL: Serial Clock Line

5b1a2a1a-pi-i2c

#math #es

Matemáticas

conjuntos

axiomas

lógica formal